No. 51 - Next Number with Same Set of Digits

Problem: Reorder the digits of a number, in order to get the next number which is the least one that is greater than the input number. For example, the number 34724126 is the next number of 34722641 when reordering digits.
 

Analysis: When a digit in a number is swapped with a greater digit on its right side, the number becomes greater. For example, if the digit 3 in the number 34722641 is swapped with digit 7, the result is 74322641 which is greater than the original number. The remaining issue how to get least number which is greater than the original one.
 

Since we are going to get the least number after reordering digits, let’s find digits to be swapped on the right side. The first three digits on the right side of 34722641 are 641 which are decreasingly sorted. The two digits among them are swapped, the whole number will become less.
 

Let’s move on to the left digits. The next digit on the right side is 2, which is less than 6 and 4 on its right side. If the digit 2 is swapped with 6 or 4, the whole number will be become greater. Since we are going to keep the swapped number as less as possible, the digit 2 is swapped with 4, which is less one between 4 and 6. The number becomes 34724621.
 

Now 34724621 is greater than the original number 34722641, but it’s not the least one which is greater than 34722641. The three digits on the right side, 6, 2 and 1, should be increasingly sorted, in order to form the least number 34724126 among numbers which are greater than of 34722641.
 

The solution can be implemented with the following JAVA code:
 

public static String getLeastGreaterNumber(String number) {

    List<Character> decreasingChars = new ArrayList();
    int firstDecreasing = getDecreasingChars(number, decreasingChars);

    if(isGreatestNumber(firstDecreasing)) {

        return "";
    }

    String prefix = "";

    if(firstDecreasing > 1) {
        prefix = number.substring(0, firstDecreasing - 1);
    }

    StringBuilder resultBuilder = new StringBuilder(prefix);

    char target = number.charAt(firstDecreasing - 1);
    char leastGreater = swapLeastGreater(decreasingChars, target);
    resultBuilder.append(leastGreater);

    Collections.sort(decreasingChars);

    appendList(resultBuilder, decreasingChars);

    return resultBuilder.toString();
}

When all digits are already increasingly sorted in the input number, the number itself is the greatest number with given digits. We should discuss with our interviewers what to return for this case during interviewers. Here we just return an empty string for this case.
 

When firstDecreasing is 0, it means all digits are increasingly sorted, and the input number is the greatest number with given digits, as listed in the following method isGreatestNumber.
 

private static Boolean isGreatestNumber(int firstDecreasing) {

    return firstDecreasing == 0;
}

The following method getDecreasingChars gets the longest sequence of decreasing digits on the right side of a number:
 

private static int getDecreasingChars(String number, List<Character> decreasing) {

    int firstDecreasing = number.length() - 1;
    for(; firstDecreasing > 0; --firstDecreasing) {
        char curChar = number.charAt(firstDecreasing);
        char preChar = number.charAt(firstDecreasing - 1);
        decreasing.add(curChar);

        if(curChar > preChar) {
            break;
        }
    }

    return firstDecreasing;

}

The following method swapLeastGreater swaps the digit before the decreasing digits on the right side (target) and the least digit which is greater than target:
 

private static char swapLeastGreater(List<Character> chars, char target) {

    Iterator it=chars.iterator();
    char finding = '9';
    while(it.hasNext()) {
        char value = ((Character)it.next()).charValue();
        if(value > target && value < finding) {
            finding = value;
        }
    }

    chars.remove(new Character(finding));
    chars.add(new Character(target));

    return finding;

}

The following method appendList appends characters from a list into a string builder:
 

private static void appendList(StringBuilder str, List<Character> chars) {

    Iterator it=chars.iterator();
    while(it.hasNext()) {
        char value = ((Character)it.next()).charValue();
        str.append(value);
    }
}

Code with unit tests is shared at http://ideone.com/czs13W.

Extended Problem 1: Given a set of digits, please output all numbers permutated by the digits in increasing order. For example, if the input are five digits 1, 2, 3, 4, 5, the output are numbers from 12345, 12354, ..., to 54321 in increasing order.
 

Extended Problem 2: Given a number n, please out put all numbers with n bits of 1 in increasing order. For example, if the input is 3, the output are numbers 7, 11, 13, …
 

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.