Amazon Interview Question
Software Engineer in Tests Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Code: h t t p://codepad.org/3yb97kQR
- Split the number into digits
- Scan from right to left (digits) till we find the digit lower than what we have passed by. Let us, call this as flip-point.
- Find 'Next Highest' of the flip-point left digit with in the flip-point right portion (not in the whole set of digits).
- Swap and flip-point left digit with 'Next Highest'.
- Now sort the digits from the flip-point onwards (and including flip-point)
- Construct the number back from digits
For example:
Input = 12345, Flip = 5, Next Highest = 5, Answer = 12354
Input = 13483, Flip = 8, Next Highest = 8, Answer = 13834
Input = 37723971, Flip = 9, Next Highest = 7, Answer = 37727139
Thanks,
Laxmi
Thanks for noticing this. I have fixed the bug in the code and edited the old comment to reflect right algorithm.
Thanks,
Laxmi
@Laxmi
is the Next highest is your algorithm the smallest number among the numbers that were passed by that is greater than the current number?
For example, If the number is 377239761. The Flip is still 9 but the next highest number greater than 3 is 6 and not 7 and so the answer should be 377261379.
'Next Highest' is the smallest number greater than the flip-point left digit with in the 'right portion' than a whole. I have clarified the text. The code is clear, but explanation is not. Sorry about that.
Thanks,
Laxmi
Hi Laxmi,
We can even remove that double for loop for " Sort the digits from flip-point onwards" into 2 single for loops.
All the numbers from flip-point until the end are in decreasing order only with one empty slot at iSort position in your code.
So we have 2 lists with decreasing numbers and just have to find a right position for nTemp and then just shift all the numbers either right or left till the iSort position is filled.
Hope you get this ;)
Yes Gaurav, you are right. Just revering right side portion and finding the right place for iSort would would do the trick.
Thanks,
Laxmi
/*I think the problem bases itself on the mathematical fact that the difference of 2 numbers consisting of same digits, is always a multiple of 9.
so, the pseudo code for this is :
0. take the input number
1. add 9 to input number
2. check if new number's digits and the input numbers digits are same.
3. if yes, then return the new number
4. if no, then
4a. if number of digits in new number > number of digits in input, then bail out and tell that the input number is the largest.
4b. else repeat 1 to 4
*/
private static void FindNextLargest()
{
int input = 100001;
int newNum = input;
int ret = 0;
do
{
newNum = newNum + 9;
ret = AreSameDigits(input, newNum);
}
while (ret != 0 && ret != -2);
Console.WriteLine(input + " => " + newNum);
}
private static int AreSameDigits(int input, int newNum)
{
ArrayList inputnums = new ArrayList(input.ToString().ToCharArray());
inputnums.Sort();
ArrayList newnums = new ArrayList(newNum.ToString().ToCharArray());
newnums.Sort();
if (newnums.Count > inputnums.Count)
return -2;
for (int i = 0; i < inputnums.Count; i++)
{
if ((char)inputnums[i] != (char)newnums[i])
{
return -1;
}
}
return 0;
}
What i did is i first sorted the number in increasing order. Say the sorted one is n and original is o.
Then starting from end,replacing the last digit of n with second last. Then checking it with original o. If its greater, then we have the solution.
Repeating this till the first digit of sorted n is replaced with second digit.
eg- o=15432, n=12345.
n= 12354,12435,13245,21345 (answer)
Hey,
This can be done as follows,
1. Find the transition point from right to left. i.e, from higher to lower. In this case the transition occurs at 1.
2. Then sort the numbers present at right of the transition point alone. In this case,
1 2345.
3. Then swap the number with the closest higher number in the right side. 2 1 345.
below is the code for that
#include<stdio.h>
void driver()
{
int digit = 0;
int arr[10] = {0};
printf("\nEnter the num\n");
scanf("%d",&digit);
int temp = digit;
int j = 0,l = 0,i = 0;
int size = 0;
while(temp)
{
arr[size++] = temp%10;
temp = temp/10;
}
for(i = 1; i < size; i++)
{
if(arr[i] < arr[i-1])
break;
}
//i contains the index of the digit to be changed
temp = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[temp])
{
temp = j;
}
}
j = arr[temp];
arr[temp] = arr[i];
arr[i] = j;
temp = i;
for(i = 0; i < temp; i++)
{
for(j = 0; j <temp; j++)
{
if(arr[i] > arr[j])
{
l = arr[j];
arr[j] = arr[i];
arr[i] = l;
}
}
}
temp = 0;
for(i = 0; i < size; i++)
{
temp = arr[size-1-i] + temp*10;
}
printf("\n%d",temp);
}
int main()
{
driver();
return 0;
}
<pre lang="" line="1" title="CodeMonkey60211" class="run-this">#include <iostream>
#include <stack>
using namespace std;
int main(int argc, char * argv[])
{
int lo,hi,num = atoi(argv[1]);
stack <int> s1,s2;
lo = num%10;
num = num/10;
s1.push(lo);
while(num != 0){
lo = num % 10;
num = num / 10;
if(lo < s1.top()){
while(!s1.empty() && s1.top() > lo){
s2.push(s1.top());
s1.pop();
}
hi = s2.top();
s2.pop();
s2.push(lo);
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
num = num*10+hi;
while(!s2.empty()){
num = num * 10 + s2.top();
s2.pop();
}
cout<<"result: "<<num<<endl;
return 0;
}
s1.push(lo);
}
cout<<"no such number exists\n";
return 1;
}
</pre><pre title="CodeMonkey60211" input="yes">
./a.out 13434</pre>
Let put every digit into an arry. Now let's iterate this arry from the tail to th front. For every digit in this arry, find the digit which is in the arrary and just bigger than the digit, if found, swap them and stop the iteration.
unsigned int FindNumber(unsinged int input)
{
std::vector<unsigned int> v;
while(input > 0)
{
v.push_back(input % 10);
input /= 10;
}
vector<unsigned int>::reverse_iterator riter = v.rbegin();
for(; iter != v.rend(); +iter)
{
vector<unsigne int>::reverse_iterator riter1 = v.rbegin();
unsigned min = 0xffffffff;
vector<unsigned int>::reverse_iterator minIter = v.rend();
for(; iter1 != v.rend(); ++ iter1)
{
if(riter != riter1 && *riter1 > *riter && *riter1 < min)
{
min = * riter1;
minIter = riter1;
}
}
if(minIter != v.rend())
{
unsigned int temp = * minIter;
*minIter = *riter;
*riter = temp;
break;
}
}
vecotr<unsigned int>:;iterator iter = v.begin();
unsigned int ret = 0
for(; iter != v.end(); ++iter)
{
ret = ret * 10 + *iter2;
}
return ret;
}
Code is not well written. Modify it a little bit. For 14235, it outputs 14253, the correct answer.
unsigned int FindNumber(unsigned int input)
{
vector<unsigned int> v;
while(input > 0)
{
v.push_back(input % 10);
input /= 10;
}
vector<unsigned int>::iterator iter = v.begin();
for(; iter != v.end(); ++iter)
{
vector<unsigned int>::iterator iter1 = v.begin();
unsigned int min = 0xffffffff;
vector<unsigned int>::iterator minIter = v.end();
for(; iter1 != iter; ++ iter1)
{
if(iter != iter1 && *iter1 > *iter && *iter1 < min)
{
min = * iter1;
minIter = iter1;
}
}
if(minIter != v.end())
{
unsigned int temp = * minIter;
*minIter = *iter;
*iter = temp;
if(iter != v.begin())
sort(v.begin(), iter, mycompare);
break;
}
}
vector<unsigned int>::reverse_iterator riter = v.rbegin();
unsigned int ret = 0;
for(; riter != v.rend(); ++riter)
{
ret = ret * 10 + *riter;
}
return ret;
}
Majority of the solutions here assuming the digits are unique. Original question poster might need to clarify that part. I guess we should also consider stuff like 33434 (ans: 33443).
This sounds to me the other problem where we need to find all numbers in sorted order for a given N. That is,
N = 1: 1
N = 2: 11, 12, 21, 22
N = 3: 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333
In this case, N = number of digits in the given number
We have to drop the sequence generation in this program after we hit the input number, and till we find the next number that uses the same digits (and the number of repetetions).
Thanks,
Laxmi
I am giving a hint to solve the problem.
at every index i starting from 0 we ask 2 questions
1. Does A[i] to A[n-1] is strictly decreasing. if not we recurse , we stop the recursion if i = n-3. at this stage if it is not strictly decreasing we can exchange n-1 and n-2.
2. if yes we stop recursion.
Below the recursive call we find out if we have returned from 1. or 2.
If we returned from 1. nothing more to be done.
if we returned from 2. a small juggling of the sorted(descending) from that index is kind of enough to solve the problem.
I have return Simple java program.
public class nexthigherValue {
public static void main(String args[]){
int givenNumber = 15432;
boolean nextHigherValFlag = false;
int givenNumberValueIncrement = givenNumber;
while(!nextHigherValFlag){
givenNumberValueIncrement++;
if(String.valueOf(givenNumberValueIncrement).length() == String.valueOf(givenNumber).length()){
String tempString = String.valueOf(givenNumberValueIncrement);
int intialIcount = 0;
String givenNumberStr = String.valueOf(givenNumber);
for(int i = tempString.length() ; i > 0 ; i--){
String charTemp = tempString.substring(i-1, i);
if(givenNumberStr.contains(charTemp)){
givenNumberStr = givenNumberStr.replaceFirst(charTemp, "");
intialIcount++;
if(intialIcount == String.valueOf(givenNumberValueIncrement).length() ){
nextHigherValFlag = true;
System.out.println("Next higher Value is:"+givenNumberValueIncrement);
}
} else{
break;
}
}
} else{
System.out.println("It is not possible");
nextHigherValFlag = true;
}
}
}
}
Scan from left to right:
For each position check for next greater number than current in all positions to its right. If exists, swap and return.
So for 15432, start from 2 (no numbers to right so skip), next 3 (no numbers greater than 3 to right), next 4 (no numbers greater than 4 to its right), next 5 (no numbers greater than 5 to its right), next 1 (2 is next greater number of all positions to its right). So swap it 21345
Scan from right to left. Find the first instance where the digit is lesser than the digit to its right. Now find the minimum of the digits to its right which is still greater than the current digit and swap them. Finally arrange everything to the digit's right in ascending order which should be very close to the reverse order so the overall complexity still remains O(n).
Do let me know if there are any errors / improvements possible in this solution.
In case of arranging remaining digits ,if i am not wrong,you will use sorting.So which sorting gives O(n) performance if i don't have to use additional space(e.g. counting sort).Could you please elaborate more?
You could use bucket sort, where you have 10 buckets (0,1 ... 9) ... since, you are sorting digits, which are all essentially in the range 0 .. 9 .. So yes, this gets reduced to counting sort in this case (since bucket size is one) ..
you end up using constant space .. Array of size 10.
When we exchange 2 digits at position i and j, we essentially change the number by amount 10^i (x-y) + 10^j(x-y).
We want this difference to be as small as possible and positive.
Hence we scan the digits from right to left to find the 1st number which is lesser than the number on it's right. We swap this with smallest number among the numbers on the right. And then re-arrange all the numbers on the right so that the bigger numbers move as far right as possible (basically in ascending order).
first find the next highest digit number. here it is 2 . Now swap this with first digit. Now number becomes 25431
second step is sort elements in ascending order from 2 position.
it's O(n+n)= (n) solution.
Sorting is not required.
while (length >= 0)
{
if (str [length] > str [length -1])
{
swap (str [length], str [length - 1]);
break;
}
swap (str [length], str [length - 1]);
--length;
}
// str - String
// length + 1 : Start index
// strlen (str) - 1 : End index
// Reverse string between start and end index
reverseString (str, length + 1, strlen (str) - 1);
Example:
15432 -> 15423 -> 15243 -> 12543 -> 21(345)
12345 -> 12354()
124875 -> 124857 -> 124587 -> 125487 -> 1254(78)
Where digits in '()' are reversed.
Complexity:
Int to String O (N) +
Find Fliping point O (N) +
Reverse substring O (N) +
String to Int O (N)
Overall: O (N)
Here is a sample code in java....
{
public class FindNextNumber
{
public static void main(String[] args)
{
FindNextNumber sF = new FindNextNumber();
long input = 342167;
System.out.println("Input Number "+input);
System.out.println("Output: \n" +
"Next Number --> "+sF.findNext(input));
}
public long reverse(long n)
{
long s = 0;
long d = n / 10;
long t = n % 10;
s = (t * 10) + d;
return s;
}
public long findNext(long k)
{
String kStr = Long.toString(k);
if (kStr.length() == 2)
{
long rev = reverse(k);
if (k < rev)
{
return rev;
}
else
{
return k;
}
}
int i = 2;
while ((i) <= kStr.length())
{
String l2 = kStr.substring((kStr.length() - i), kStr.length());
long rem = k - Long.valueOf(l2);
long newVal = 0;
if (l2.length() == 2)
{
newVal = rem + reverse(Long.valueOf(l2));
}
else
{
newVal = rem + Long.valueOf(getNext(l2));
}
if (newVal > k)
{
return newVal;
}
i++;
}
return k;
}
public String getNext(String s)
{
long first = Long.valueOf("" + s.charAt(0));
char[] charArray = s.toCharArray();
Arrays.sort(charArray);
String sorted = new String(charArray);
long m = -99;;
for (int i = 0; i < sorted.length(); i++)
{
long c = Long.valueOf("" + sorted.charAt(i));
if (c > first)
{
m = c;
break;
}
}
if (m != -99)
{
sorted = sorted.replaceFirst(Long.toString(m), "");
sorted = Long.toString(m) + sorted;
return sorted;
}
else
{
return s;
}
}
}
}
friends let me know if this will work....
i have a way to solve the problem. i kind of solves many cases but fails in one case. when the number is 13483 the answer should be 13834 but my program returns 31348. please have a look at my program and please suggest if we can improve it.
int given = 15432;
String s = Integer.toString(given);
int [] arr = new int[s.length()];
for(int i=0; i<s.length(); i++){
arr[s.length()-1-i] = given%10;
given = given/10;
}
System.out.println("\n");
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]);
}
boolean flag = true;
int k = 0;
int ii = (arr.length-1);
while(ii>=0 && flag==true){
for(k=ii-1; k>=0; k--){
if(arr[k] < arr[ii]){
int temp = arr[ii];
arr[ii] = arr[k];
arr[k] = temp;
flag = false;
break;
}
}
ii--;
}
System.out.println("\n");
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]);
}
quicksort(arr, k+1, arr.length-1);
System.out.println("\n");
for(int i=0; i<arr.length; i++){ System.out.print(arr[i]); }
Below is the implementation of the algorithm in c++ with all the descriptions inlined as comments:
template <class T>
void __swap(T& left, T& right)
{
T tmp;
tmp = left;
left = right;
right = tmp;
}
bool digs_to_int(char dat[], int elcount, int& val)
{
int retv = 0;
if (0 == elcount)
return false;
val = -1;
for (int i = 0; i < elcount; i++){
retv = retv * 10 + dat[i];
}
val = retv;
return true;
}
/**
- start scanning from the right at position (elcount - 1) and find the digit
with index @i such that d[i] < d[i+1];
- sort the array from @i+1 to @elcount
- from position @i+1 find the smallest digit such that d[i]<d[smallest_digit_pos]
- swap(d[i], d[smallest_digit_pos])
@dat - the array of chars with the number digits
@elcount - count of elements in the array
*/
bool next_max_val(char dat[], int elcount, int& nxtmax)
{
int i;
int minidx; // index of the first value on the right of the pivot that is greater than the pivot value
int pividx; // the pivot index
int eidx; // the last index of the array
nxtmax = -1;
eidx = elcount - 1;
pividx = -1; // initially set to invalid index (not found)
minidx = -1;
/* Find the digit that is less than its successor digit. */
for (i = eidx - 1; i >= 0; i--) {
if (dat[i] < dat[i + 1]) {
pividx = i;
break;
}
}
/* If there is no such digit then this is the maximum value */
if (-1 == pividx) {
digs_to_int(dat, elcount, nxtmax);
printf("This is the maximum number: %d\n", nxtmax);
return true;
}
/* Sort the array starting from the element next to the pivot */
std::sort(dat + pividx + 1, dat + eidx + 1);
/* Find the first digit in the rest of the sorted digits that is > than
the pivot value at dat[pividx]*/
for (i = pividx + 1; i < elcount; i++) {
if (dat[pividx] < dat[i]) {
minidx = i;
break;
}
}
/* Swap the pivot value and the minimal value in the rest of the
* sorted array. */
__swap(dat[i], dat[pividx]);
digs_to_int(dat, elcount, nxtmax);
return true;
}
Works with all the test cases that were provided in the comments, code is in JAVA
public int nextHigherWithSameDigits(int number)
{
char[] digits = String.valueOf(number).toCharArray();
int length = digits.length;
int i;
for(i = length - 1; i > 0; i--)
{
if(digits[i-1] < digits[i])
{
break;
}
}
if(i > 0)
{
char minChar = digits[length -1];
int position = length - 1;;
for(int k = length - 2; k >= i; k--)
{
if(minChar > digits[k] || minChar < digits[i-1])
{
minChar = digits[k];
position = k;
}
}
char temp = digits[position];
digits[position] = digits[i-1];
digits[i-1] = temp;
char[] subDigits = new char[digits.length - i];
int j = 0;
for(int index = i; index < length; index++)
{
subDigits[j++] = digits[index];
}
Arrays.sort(subDigits);
j = 0;
for(int index = i; index < length; index++)
{
digits[index] = subDigits[j++];
}
number = Integer.parseInt(new String(digits));
}
return number;
}
def nextHighest(n):
na = intToArray(n)
for i in range(1, len(na)):
sbiggeri = smallestBigger(na[i], i, na)
if sbiggeri > -1:
swap(i, sbiggeri, na)
break
return intArrayToInt(na)
# returns -1 if it cannot find a smallest digit which is greater than d
def smallestBigger(d, h, na): # h is exclusive
mind = 10
mini = -1
for i in range(h):
if na[i] > d and na[i] < mind:
mind = na[i]
mini = i
return mini
def countDigist(n):
nd = 1
n = n / 10
while n != 0:
nd += 1
n = n / 10
return nd
def intToArray(n):
c = countDigist(n)
na = []
for _ in range(c):
di = n % 10
n = n / 10
na.append(di)
return na
def intArrayToInt(na):
n = 0
for i in range(len(na)):
n += na[i] * pow(10, i)
return n
def swap(i, j, a):
tmp = a[i]
a[i] = a[j]
a[j] = tmp
private static char[] high(int num){
char[] ch = Integer.toString(num).toCharArray();
int point = ch.length-1;
String sRev = "";
Boolean isSwapped = false;
//Find the pivot point as well as store the asc order number
for(;point >0 && ch[point]<ch[point-1];point--)
sRev = sRev + ch[point];
sRev = sRev + ch[point];
char[] rev = sRev.toCharArray();
point--;
//swap the pivot number with next higher number as well as place asc ordered numbers
for(int i=0;i<rev.length;i++){
char tmp = rev[i];
if(!isSwapped && ch[point]<rev[i]){
tmp = ch[point];
ch[point] = rev[i];
isSwapped = true;
}
ch[point+i+1] = tmp;
}
return ch;
}
//I've tested the following program. I think it is correct
//I've included the main method, so you can try it directly
//Assuming input is n, and n(0) represent MSB of n
//The logic is first scan the number from LSB to MSB
//Find the first decreasing n (i) > n (i+1);
//Scan from i to 0 to find if there is a n(i)>n (j) > n(i+1);
// if there is swap the value on j and i + 1, otherwise swap i and i+1
// For example: 322431. From right to left, 1 to 3 increase, to 4 increase
// to 2 decrease, so scan back and find 3 is larger than 2 and smaller than 4
// so swap 2 and 3, we got 323421.
// Exception if there is no decreasing like 54321, there is no such a number
// just return -1
public class findNextValue {
public static int findNext (int number ){
int MAX_NUMBER_OF_DIGITS = 10; // 32-bit integer max
// value is 2,147,483,647
int [] temp = new int [MAX_NUMBER_OF_DIGITS]; // storing scaned digit
int dig = 10;
temp [0] = number % dig; // first digit
int counter = 1;
boolean found = false;
// scan from right to left to find a decreasing point
while (number * 10 > dig){
int t = number - (number / (dig * 10)) * (dig * 10);
t /= dig; // get current digit
temp [counter] = t;
if (temp[counter-1] > t){ // compare with last digit to see if there is a decrease
found = true;
counter ++;
break;
}
counter ++;
dig = dig * 10;
}
if (!found){
return -1; // no decreasing no such a number
}
int swapIndex = counter - 2; // the candidate to swap is the last one
// find if there is a smaller one to swap
for (int i = 0 ; i< counter ; i++){
if (temp [i] > temp [counter -1]){
if (temp[i] < temp[swapIndex]){
swapIndex = i;
}
}
}
swap (temp, swapIndex, counter-1);
int sum = 0;
dig = 1;
// calculate new value of the scanned part
for (int i = 0 ; i < counter ;i ++){
sum += temp[i] * dig;
dig = dig * 10;
}
// for the orginal number trim the old scanned part then add new scanned part
number = (number / dig) * dig + sum;
return number;
}
public static void swap (int arr[], int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main (String args[]){
System.out.println(findNext (322431));
}
}
Using recursion and Permutations
class Program
{
static void Main(string[] args)
{
int number = 15432;
Next(number);
Console.Read();
}
public static void Next(int number)
{
int max = 0;
Permutation(number.ToString().ToCharArray(), 0,ref max,number);
Console.WriteLine("Next Higher Number: {0}", max);
Console.Read();
}
private static void Permutation(char[] input, int current, ref int max, int number)
{
if (current == input.Length - 1)
{
int temp = int.Parse(new string(input));
if (temp > number && temp < max)
{
max = temp;
//Console.WriteLine("Current number: {0}, Current max: {1}", new string(input), max);
}
else if (temp > number && max == 0)
{
max = temp;
}
return;
}
Permutation(input, current + 1,ref max, number);
for (int i = current + 1; i < input.Length; i++)
{
char temp = input[current];
input[current] = input[i];
input[i] = temp;
Permutation(input, current + 1,ref max,number);
}
}
}
/*
scan digits from right to left (n to 1) keep track of count for each digit
if digit(i-1) < digit(i) replace digit(i-1) with the minimum most digit in digit(i...n)
.. then populate n to i with the count array using the msd of the count array
O(N)
*/
public static int findNext(int number) {
char arr[] = String.valueOf(number).toCharArray();
int count[] = new int[10];
for(int i = arr.length - 1; i > 0; i--) {
int digit = Integer.valueOf(String.valueOf(arr[i]));
int nextDigit = Integer.valueOf(String.valueOf(arr[i-1]));
count[digit]++;
if(digit > nextDigit) {
for(int j = nextDigit + 1; j < count.length; j++) {
if(count[j] > 0) { // this is the digit to be replaced
count[nextDigit]++;
count[j]--;
String numStr = String.valueOf(Arrays.copyOfRange(arr, 0, i-1)) + j; // from 0...i-2+j
for(int k = 0; k < count.length; k++) { // drain lowest first
while(count[k] > 0) {
numStr = numStr + k;
count[k]--;
}
}
return Integer.valueOf(numStr);
}
}
}
}
throw new IllegalArgumentException("Can not find a next greater number using " + number);
}
import java.util.Arrays;
public class NextLargestNumber1 {
private static int findNextLargest(int number) {
int[] digits = getDigits(number);
int rightIndex = -1;
int leftIndex = -1;
// Find the indices of the digits to be swapped.
for (int i = digits.length - 1; i > 0; i--) {
for (int j = i - 1; j >= 0; j--) {
if (digits[i] > digits[j]) {
if (rightIndex == -1) {
rightIndex = i;
leftIndex = j;
} else if (leftIndex < j && rightIndex > i) {
rightIndex = i;
leftIndex = j;
}
break;
}
}
}
if (rightIndex == -1)
throw new RuntimeException(
"Not possible to make next greater number. Input number is the greatest number that can be formed from the digits.");
swap(digits, rightIndex, leftIndex);
sort(digits, leftIndex + 1);
return formNumber(digits);
}
private static int[] getDigits(int number) {
int[] digitsArr = new int[String.valueOf(number).length()];
int index = digitsArr.length - 1;
while (number > 0) {
digitsArr[index--] = number % 10;
number = number / 10;
}
return digitsArr;
}
private static void swap(int[] digits, int rightIndex, int leftIndex) {
int temp = digits[rightIndex];
digits[rightIndex] = digits[leftIndex];
digits[leftIndex] = temp;
}
private static void sort(int[] digits, int startIndex) {
int endIndex = digits.length;
if (startIndex == endIndex)
return;
// Sort array from start index to end index
Arrays.sort(digits, startIndex, endIndex);
}
private static int formNumber(int[] digits) {
int digit = 0;
int size = digits.length;
for (int i = 0; i < size; i++)
digit = digit * 10 + digits[i];
return digit;
}
public static void main(String[] args) {
int number = 1342;
System.out.println("Input number is: " + number);
try {
int nextLargest = findNextLargest(number);
System.out.println("Next largest number is: " + nextLargest);
} catch (RuntimeException ex) {
System.out.println(ex.getMessage());
}
}
}
package com.javafries.number;
import java.util.Arrays;
public class NextLargestNumber1 {
private static int findNextLargest(int number) {
int[] digits = getDigits(number);
int rightIndex = -1;
int leftIndex = -1;
// Find the indices of the digits to be swapped.
for (int i = digits.length - 1; i > 0; i--) {
for (int j = i - 1; j >= 0; j--) {
if (digits[i] > digits[j]) {
if (rightIndex == -1) {
rightIndex = i;
leftIndex = j;
} else if (leftIndex < j && rightIndex > i) {
rightIndex = i;
leftIndex = j;
}
break;
}
}
}
if (rightIndex == -1)
throw new RuntimeException(
"Not possible to make next greater number. Input number is the greatest number that can be formed from the digits.");
swap(digits, rightIndex, leftIndex);
sort(digits, leftIndex + 1);
return formNumber(digits);
}
private static int[] getDigits(int number) {
int[] digitsArr = new int[String.valueOf(number).length()];
int index = digitsArr.length - 1;
while (number > 0) {
digitsArr[index--] = number % 10;
number = number / 10;
}
return digitsArr;
}
private static void swap(int[] digits, int rightIndex, int leftIndex) {
int temp = digits[rightIndex];
digits[rightIndex] = digits[leftIndex];
digits[leftIndex] = temp;
}
private static void sort(int[] digits, int startIndex) {
int endIndex = digits.length;
if (startIndex == endIndex)
return;
// Sort array from start index to end index
Arrays.sort(digits, startIndex, endIndex);
}
private static int formNumber(int[] digits) {
int digit = 0;
int size = digits.length;
for (int i = 0; i < size; i++)
digit = digit * 10 + digits[i];
return digit;
}
public static void main(String[] args) {
int number = 1342;
System.out.println("Input number is: " + number);
try {
int nextLargest = findNextLargest(number);
System.out.println("Next largest number is: " + nextLargest);
} catch (RuntimeException ex) {
System.out.println(ex.getMessage());
}
}
}
This seems to perform reasonably good
uint64_t
next_big(uint64_t big)
{
int start, end;
uint64_t t, t2;
if (big == 0)
return (0);
if (big == UINT64_MAX)
return (big);
start = __builtin_ffsl(big);
end = __builtin_ctzl(~(big | ((1ULL << start) - 1)));
t = big & ~((1ULL << (end)) -1);
t2 = (1ULL << (end)) | ((1ULL << (end - start)) - 1);
#ifdef TEST
int b1, b2;
uint64_t nb;
nb = (big & t) | t2;
printf("big: 0x%lx start: %d end: %d t: 0x%lx t2: 0x%lx 0x%lx\n",
big, start, end, t, t2, (big & t) | t2);
b1 = __builtin_popcount(big);
b2 = __builtin_popcount(nb);
printf("0x%lx 0x%lx %s\n", big, nb, nb > big ? "true" : "false");
#endif
return ((big & t) | t2);
}
- jazz wholer November 15, 2013