Next Bigger Integer
Given a number, find the next bigger integer composed of the same digits as the original one.
Example: 34265 -> 34526
The idea is to find the pivot meaning the point where a digit is lower than the next one. Starting from that point and until the end of the digit array, every position will be changed.
I will use a queue, put all ascending digits in it and find the first one bigger than the inflexion point. It will be that digit that will replace the value at the inflexion point.
For our example, the pivot is 2 and it will be replaced with the lowest digit found when enumerating the digits from the right, which is 5.
From there on, the number will be assembled by using the original left part and on the right we will try to build the smallest possible number by dequing the digits stored previously.
The code below:
public static int GetNextBiggerInteger(int n) { if (n < 10) { return n; } // last digit int digit = n % 10; // queue storing digits that will be moved var queue = new Queue(); queue.Enqueue(digit); n /= 10; while (n > 0) { int tempDigit = n % 10; n /= 10; if (tempDigit > digit) { queue.Enqueue(tempDigit); digit = tempDigit; } else { // found the rotation point if (n > 0) { // set the left part using the digits already stored in the queue n *= (int) Math.Pow(10, queue.Count + 1); } // right part consists on retrieving digits stored in the queue // and assembling them int result = 0; int pos = 0; // switching the pivot bool switched = false; while (!switched || queue.Count > 0) { int el = queue.Dequeue(); pos++; result *= 10; if (!switched && el > tempDigit) { result += tempDigit; result += el * (int)Math.Pow(10, pos); switched = true; } else if (switched || el < tempDigit) { result += el; } } return n + result; } } return -1; }
More examples:
21765 --> 25167 27865 --> 28567 25468 --> 25486 34265 --> 34526 54321 --> -1