# Interview Questions

# Nearest number with non-decreasing digits

- April 10, 2017
- Posted by: Kamal Rawat
- Category: Algorithms

Given a number N given in the form of array, with each index storing one digit of the number. Write code to change the number to the greatest number less than N, such that digits of that number are in non-decreasing order.

For example:

INPUT ARRAY: {1, 4, 3} (representing number 143) OUTPUT : 139 INPUT ARRAY: {2, 2, 2, 1} (representing number 2221) OUTPUT : 1999

**Solution-1: Brute Force**

The brute force approach is keep reducing the number (given in the form of array) unless the digits fall in the required order. For example, if number is 143, then we keep decrementing it by 1 and check if the digits are sorted in ascending order

ARRAY NUMBER ARE DIGITS SORTED {1, 4, 2} 142 NO {1, 4, 1} 141 NO {1, 4, 0} 140 NO {1, 3, 9} 139 YES

The answer is when the digits in array are in non-decreasing order. This solution will take lot of time (Checking the number at each step is also an added overhead.

**Solution-2:**

The logic is as below:

1. From the left side, find the first position of mismatch (where arr[i] > arr[i+1]). 2. Decrease the digit at index i and set all the digits from (i+1) till the end equal to '9'. 3. After point 2. the number after index i (including i) is in right order. But by decreasing arr[i], we might have created a mismatch between digit i and (i-1). Consider 2221, step-2 will make it 2219, and there is a mismatch at position (i-1) and i. Move back from i down to 0 and correct the mismatch if found.

Code:

import java.util.Scanner; public class RitambharaTech { public static void printNearestNonDecreasing(char[] str) { // Single Digit number if(str.length==1) { System.out.println(str); return; } int i=0; // Setting all digits after first mismatch to 9. for(; i<str.length-1; i++) { if(str[i] > str[i+1]) { for(int j=i+1; j<str.length; j++) str[j] = '9'; break; } } // Check mismatch at (i-1) and i if(i==str.length-1) System.out.println(str); else { str[i]--; for(int j=i; j>0; j--) { if(str[j-1]>str[j]) { str[j] = '9'; str[j-1]--; } } // Ignoring leading zeros while printing for(i=0; i<str.length; i++) if(str[i] != '0') break; for(; i<str.length; i++) System.out.print(str[i]); System.out.println(""); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); printNearestNonDecreasing(str.toCharArray()); } }

The above code takes O(n) time and constant extra memory.