This was asked to me in an interview a long long time ago.
The question seems easy at first sight – Find next higher number with the same digits: i.e.:
- 16823 – 16832
- 79416- 79461
- 59351- 59513
You can see how the first two examples, can give the wrong idea, that you always have to swap only 1 digit with the other. Needless to say, that is not the case… In fact as I always preach. Get clarifications! This is crucial to doing well in the software industry. You might write amazing code, but if it doesn’t do exactly what someone else needs, then chances are, you are the only one who is going to use that piece of software. The biggest clarification in this case is – what happens when we already have the highest number? Well in that case we can agree to just pass back the original number.
Now that we have our clarifications out of the way, let’s get to trying to solve our problem in a standard naive approach –
Naive approach algorithm to find next higher number with same digits
- Find all permutations of these digits
- Sort them in an array
- Find your number and return the next to that one
However, as it usually turns out, writing out the standard, naive approach is not the best one can do. Let’s do a very small analysis. Time-wise is what we are concerned the most. A number N will have log(N) digits. Therefore to create all permutations, we will need O(log(N)!) or otherwise O(nlog(n)), (to refresh why, check Common BigO).
To sort it, we will need O(log(n)!log(log(n)!), which translates to O(nlog(n)log(n))
As you can see it’s not quite ideal. And note that we are accounting for n as the number itself…. If n was the number of digits our Time complexity would “appear” much higher.
For a different algorithm, let’s take an example: 1287431. Starting from the right-most digit we want to go left until we find a number smaller than the previous (Therefore having the possibility to swap it and making a bigger number). Therefore in our number we go left until we hit 2 (2 < 8). When we hit 2, we want to swap it, we want to swap it with the smallest number that we have seen so far, higher than 2, which is 3. Therefore we swap 3 with 2 and our number now looks like this – 1387421. For the rest we just need to sort the digits we saw and we are done. Our final number will be 1312478. Great! Now let’s put this into a concise algorithm:
Revised algorithm to find next higher number with same digits
- Find the rightmost digit pair such that i < j and indexOf(i) < indexOf(j)
- Swap i with the k, the smallest digit to the right of j
- Sort all elements to the right of k
Great! If you followed me to this point then you know that all that is left is put this into some coding…..
First real try to find next higher number with same digits
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
public int findNextHigher(int nTarget) { StringBuffer sTarget = new StringBuffer(String.valueOf(nTarget)); int nLength = sTarget.length(); int nDigitIndex = nLength - 2; //Note that we start to the second last to avoid Array out of Bounds boolean bPivotFound = false; int nPivotIndex = -1; int nNextHigherIndex = -1; char cPivot = '-'; char cNextHigher = '-'; // Find the pivot where our digit becomes lower. while (nDigitIndex >= 0) { if (sTarget.charAt(nDigitIndex) < sTarget.charAt(nDigitIndex + 1)) { bPivotFound = true; nPivotIndex = nDigitIndex; cPivot = sTarget.charAt(nPivotIndex); nNextHigherIndex = nPivotIndex + 1; // We are guaranteed that this is higher than our Pivot. cNextHigher = sTarget.charAt(nDigitIndex); break; } --nDigitIndex; } if (!bPivotFound) { return nTarget; // Target is the highest number with its digits. } while (nDigitIndex < nLength) { if ((sTarget.charAt(nDigitIndex) > cPivot) && (sTarget.charAt(nDigitIndex) < cNextHigher)) { nNextHigherIndex = nDigitIndex; cNextHigher = sTarget.charAt(nDigitIndex); } } // Swap pivot with nextHigher sTarget.setCharAt(nPivotIndex, cNextHigher); sTarget.setCharAt(nNextHigherIndex, cPivot); // sort the substring starting at nPivotIndex + 1 char[] tempSubSequence = new char[nLength - nPivotIndex + 1]; sTarget.getChars(nPivotIndex, nLength, tempSubSequence, 0); Arrays.sort(tempSubSequence); sTarget.replace(nPivotIndex, nLength, new String(tempSubSequence)); return Integer.valueOf(sTarget.toString()); } |
If you have followed enough of my posts, you should surely know that writing a first solution at a problem is not enough. Indeed the code above is pretty ugly for my taste and it can be refactored in many ways. This time however, I will not post a second try at rewriting it, but instead will leave you up to the task… In what ways can we rewrite the method to make it more readable and potentially more efficient?
Hope you guys enjoyed it… And I’ll see you guys next time ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017
I believe you can use two “min heap”s , go through the digits from right to left, adding them to the heap no 1 till you find one number bigger smaller than the previous, then to find the replacement you start checking for the first bigger digit in heap no 1, if it’s not there you remove min from heap no 1 add it to heap no 2 till found. then add the rest plus the swapped no. to heap no 2. then you fill the right hand side from left to right from no heap 2 and it will be already sorted.
Good call. I think it`s the same idea. In the algo above we just use a String + charArray (for Sorting) instead of the two heaps.