## Amazon Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Does the question ask for the least number which is greater than the given number and is also the permutation of it?

I think it requires flipping the first instance of arr[i] < arr[i+1], starting from units position. The idea is to make the least significant two digits more than it's current value. (Comments?)

retNextPermute(char* num) //assuming the num to be string.

{

int len = strlen(num);

for(; len > 1; len--)

{

//compare the two digits

int x = num[len-1] - '0';

int y = num[len-2] - '0';

if(x > y)

{

//flip the digits if condition satisfy and break

char tmp = num[len-1];

num[len-1] = num[len-2];

num[len-2] = tmp;

break;

}

}

//print the num

}

let us from an array which consists of digits of the given number as its element

for ex: number = 1234 then our array would be, arr[] = {1, 2, 3, 4}; and N = 4(length of array)

Then we do following steps to get the nextPermutation

1) find the highest index i such that arr[i] < arr[i+1];

2) next we find highest index j > i (found in step 1) , such that arr[j] > arr[i] , such j is sure to exist because we already have it as i+1 , we want the highest index

3)swap arr[i], arr[j].

4)reverse the array arr from index i+1 to N

and we get our next permutation

following code implements , the above algorithm

It takes as input the array arr and its length

- Anurag Gupta April 16, 2012