Data Modelling & AI Data Structure & Algorithm

Make the list non-decreasing by changing only one digit of the elements

23 June 2025

0

Given an array arr[] of N integers where every element is from the range [1000, 9999]. The task is to make the array non-decreasing by changing only one digit from the array elements and the elements of the resultant list will have to be from the given range of elements. If it is possible to make the array non-decreasing with the given operation then print the updated list otherwise print -1.

Examples:

Input: arr[] = {1095, 1094, 1095}
Output: 1005 1014 1015
1095 -> 1005
1094 -> 1014
1095 -> 1015
1005 ? 1014 ? 1015

Input: arr[] = {5555, 4444, 3333, 2222, 1111}
Output: 1555 2444 3033 3222 4111

Approach: The idea is to change a digit of the first element to make it as small as possible. To do that, start from 1000 and store the smallest number for which at most 1 digit needs to be changed. Similarly, for the next element find the smallest possible number, not less than the previous one for which the number of change of digit is at most 1. If the last element doesn’t exceed 9999 then the list is possible.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int DIGITS = 4, MIN = 1000, MAX = 9999;
 
// Function to return the minimum element
// from the range [prev, MAX] such that
// it differs in at most 1 digit with cur
int getBest(int prev, int cur)
{
    // To start with the value
    // we have achieved in the last step
    int maximum = max(MIN, prev);
 
    for (int i = maximum; i <= MAX; i++) {
        int cnt = 0;
 
        // Store the value with which the
        // current will be compared
        int a = i;
 
        // Current value
        int b = cur;
 
        // There are at most 4 digits
        for (int k = 0; k < DIGITS; k++) {
 
            // If the current digit differs
            // in both the numbers
            if (a % 10 != b % 10)
                cnt += 1;
 
            // Eliminate last digits in
            // both the numbers
            a /= 10;
            b /= 10;
        }
 
        // If the number of different
        // digits is at most 1
        if (cnt <= 1)
            return i;
    }
 
    // If we can't find any number for which
    // the number of change is less than or
    // equal to 1 then return -1
    return -1;
}
 
// Function to get the non-decreasing list
void getList(int arr[], int n)
{
    // Creating a vector for the updated list
    vector<int> myList;
 
    int i, cur;
 
    // Let's assume that it is possible to
    // make the list non-decreasing
    bool possible = true;
 
    myList.push_back(0);
 
    for (i = 0; i < n; i++) {
 
        // Element of the original array
        cur = arr[i];
 
        myList.push_back(getBest(myList.back(), cur));
 
        // Can't make the list non-decreasing
        if (myList.back() == -1) {
            possible = false;
            break;
        }
    }
 
    // If possible then print the list
    if (possible) {
        for (i = 1; i < myList.size(); i++)
            cout << myList[i] << " ";
    }
 
    else
        cout << "-1";
}
 
// Driver code
int main()
{
    int arr[] = { 1095, 1094, 1095 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    getList(arr, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static int DIGITS = 4, MIN = 1000, MAX = 9999;
 
// Function to return the minimum element
// from the range [prev, MAX] such that
// it differs in at most 1 digit with cur
static int getBest(int prev, int cur)
{
    // To start with the value
    // we have achieved in the last step
    int maximum = Math.max(MIN, prev);
 
    for (int i = maximum; i <= MAX; i++) 
    {
        int cnt = 0;
 
        // Store the value with which the
        // current will be compared
        int a = i;
 
        // Current value
        int b = cur;
 
        // There are at most 4 digits
        for (int k = 0; k < DIGITS; k++) 
        {
 
            // If the current digit differs
            // in both the numbers
            if (a % 10 != b % 10)
                cnt += 1;
 
            // Eliminate last digits in
            // both the numbers
            a /= 10;
            b /= 10;
        }
 
        // If the number of different
        // digits is at most 1
        if (cnt <= 1)
            return i;
    }
 
    // If we can't find any number for which
    // the number of change is less than or
    // equal to 1 then return -1
    return -1;
}
 
// Function to get the non-decreasing list
static void getList(int arr[], int n)
{
    // Creating a vector for the updated list
    Vector<Integer> myList = new Vector<Integer>();
 
    int i, cur;
 
    // Let's assume that it is possible to
    // make the list non-decreasing
    boolean possible = true;
 
    myList.add(0);
 
    for (i = 0; i < n; i++) 
    {
 
        // Element of the original array
        cur = arr[i];
 
        myList.add(getBest(myList.lastElement(), cur));
 
        // Can't make the list non-decreasing
        if (myList.lastElement() == -1) 
        {
            possible = false;
            break;
        }
    }
 
    // If possible then print the list
    if (possible) 
    {
        for (i = 1; i < myList.size(); i++)
            System.out.print(myList.get(i) + " ");
    }
 
    else
        System.out.print("-1");
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1095, 1094, 1095 };
    int n = arr.length;
 
    getList(arr, n);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach 
DIGITS = 4; MIN = 1000; MAX = 9999; 
 
# Function to return the minimum element 
# from the range [prev, MAX] such that 
# it differs in at most 1 digit with cur 
def getBest(prev, cur) : 
 
    # To start with the value 
    # we have achieved in the last step 
    maximum = max(MIN, prev); 
 
    for i in range(maximum, MAX + 1) :
        cnt = 0; 
 
        # Store the value with which the 
        # current will be compared 
        a = i; 
 
        # Current value 
        b = cur; 
 
        # There are at most 4 digits 
        for k in range(DIGITS) :
 
            # If the current digit differs 
            # in both the numbers 
            if (a % 10 != b % 10) :
                cnt += 1; 
 
            # Eliminate last digits in 
            # both the numbers 
            a //= 10; 
            b //= 10; 
 
        # If the number of different 
        # digits is at most 1 
        if (cnt <= 1) :
            return i; 
 
    # If we can't find any number for which 
    # the number of change is less than or 
    # equal to 1 then return -1 
    return -1; 
 
# Function to get the non-decreasing list 
def getList(arr, n) : 
 
    # Creating a vector for the updated list 
    myList = [];
     
    # Let's assume that it is possible to
    # make the list non-decreasing
    possible = True; 
 
    myList.append(0); 
 
    for i in range(n) :
 
        # Element of the original array 
        cur = arr[i]; 
 
        myList.append(getBest(myList[-1], cur)); 
 
        # Can't make the list non-decreasing 
        if (myList[-1] == -1) : 
            possible = False; 
            break;
 
    # If possible then print the list 
    if (possible) : 
        for i in range(1, len(myList)) :
            print(myList[i], end = " "); 
    else :
        print("-1"); 
 
# Driver code 
if __name__ == "__main__" : 
 
    arr = [ 1095, 1094, 1095 ]; 
    n = len(arr); 
 
    getList(arr, n); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;             
 
class GFG
{
static int DIGITS = 4, MIN = 1000, MAX = 9999;
 
// Function to return the minimum element
// from the range [prev, MAX] such that
// it differs in at most 1 digit with cur
static int getBest(int prev, int cur)
{
    // To start with the value
    // we have achieved in the last step
    int maximum = Math.Max(MIN, prev);
 
    for (int i = maximum; i <= MAX; i++) 
    {
        int cnt = 0;
 
        // Store the value with which the
        // current will be compared
        int a = i;
 
        // Current value
        int b = cur;
 
        // There are at most 4 digits
        for (int k = 0; k < DIGITS; k++) 
        {
 
            // If the current digit differs
            // in both the numbers
            if (a % 10 != b % 10)
                cnt += 1;
 
            // Eliminate last digits in
            // both the numbers
            a /= 10;
            b /= 10;
        }
 
        // If the number of different
        // digits is at most 1
        if (cnt <= 1)
            return i;
    }
 
    // If we can't find any number for which
    // the number of change is less than or
    // equal to 1 then return -1
    return -1;
}
 
// Function to get the non-decreasing list
static void getList(int []arr, int n)
{
    // Creating a vector for the updated list
    List<int> myList = new List<int>();
 
    int i, cur;
 
    // Let's assume that it is possible to
    // make the list non-decreasing
    bool possible = true;
 
    myList.Add(0);
 
    for (i = 0; i < n; i++) 
    {
 
        // Element of the original array
        cur = arr[i];
 
        myList.Add(getBest(myList[myList.Count - 1], cur));
 
        // Can't make the list non-decreasing
        if (myList[myList.Count - 1] == -1) 
        {
            possible = false;
            break;
        }
    }
 
    // If possible then print the list
    if (possible) 
    {
        for (i = 1; i < myList.Count; i++)
            Console.Write(myList[i] + " ");
    }
 
    else
        Console.Write("-1");
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1095, 1094, 1095 };
    int n = arr.Length;
 
    getList(arr, n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
var DIGITS = 4, MIN = 1000, MAX = 9999;
 
// Function to return the minimum element
// from the range [prev, MAX] such that
// it differs in at most 1 digit with cur
function getBest(prev, cur)
{
     
    // To start with the value
    // we have achieved in the last step
    var maximum = Math.max(MIN, prev);
 
    for(var i = maximum; i <= MAX; i++)
    {
        var cnt = 0;
         
        // Store the value with which the
        // current will be compared
        var a = i;
 
        // Current value
        var b = cur;
 
        // There are at most 4 digits
        for(var k = 0; k < DIGITS; k++)
        {
             
            // If the current digit differs
            // in both the numbers
            if (a % 10 != b % 10)
                cnt += 1;
 
            // Eliminate last digits in
            // both the numbers
            a = parseInt(a / 10);
            b = parseInt(b / 10);
        }
 
        // If the number of different
        // digits is at most 1
        if (cnt <= 1)
            return i;
    }
 
    // If we can't find any number for which
    // the number of change is less than or
    // equal to 1 then return -1
    return -1;
}
 
// Function to get the non-decreasing list
function getList(arr, n)
{
     
    // Creating a vector for the updated list
    var myList = [];
 
    var i, cur;
 
    // Let's assume that it is possible to
    // make the list non-decreasing
    var possible = true;
 
    myList.push(0);
 
    for(i = 0; i < n; i++) 
    {
         
        // Element of the original array
        cur = arr[i];
 
        myList.push(getBest(
            myList[myList.length - 1], cur));
 
        // Can't make the list non-decreasing
        if (myList[myList.length - 1] == -1)
        {
            possible = false;
            break;
        }
    }
 
    // If possible then print the list
    if (possible) 
    {
        for(i = 1; i < myList.length; i++)
            document.write( myList[i] + " ");
    }
    else
        document.write("-1");
}
 
// Driver code
var arr = [ 1095, 1094, 1095 ];
var n = arr.length;
 
getList(arr, n);
 
// This code is contributed by itsok
 
</script>

Output:

1005 1014 1015

Time Complexity: O(n + (MAX * DIGITS)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Make the list non-decreasing by changing only one digit of the elements

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Google defends Android’s controversial sideloading policy

Nothing’s new AI Tools let you build apps with just a prompt

Apple iPhone 17 Pro Max review: As subtle as a sledgehammer, and just as powerful

The offline Google Maps routine that saves me on every road trip

EDITOR PICKS

Google defends Android’s controversial sideloading policy

Nothing’s new AI Tools let you build apps with just a prompt

Apple iPhone 17 Pro Max review: As subtle as a sledgehammer, and just as powerful

POPULAR POSTS

Google defends Android’s controversial sideloading policy

Nothing’s new AI Tools let you build apps with just a prompt

Apple iPhone 17 Pro Max review: As subtle as a sledgehammer, and just as powerful

POPULAR CATEGORY

ABOUT US

FOLLOW US