**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.**

__Problem:__**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.**

__Analysis:__
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);

}

}

**: 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 1__**Given a number**

__Extended Problem 2:__*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.

## No comments:

## Post a Comment