Given a number, find the next higher number which has the exact same set of digits as the original number

I just bombed an interview and made pretty much zero progress on my interview question.

> Given a number, find the next higher number which has the exact same > set of digits as the original number. For example: given 38276 return > 38627

I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

The interviewer also suggested trying to swap digits one at a time, but I couldn't figure out the algorithm and just stared at a screen for like 20-30 minutes. Needless to say, I think I'm going to have to continue the job hunt.

You can do it in O(n) (where n is the number of digits) like this:

Starting from the right, you find the first pair-of-digits such that the left-digit is smaller than the right-digit. Let's refer to the left-digit by "digit-x". Find the smallest number larger than digit-x to the right of digit-x, and place it immediately left of digit-x. Finally, sort the remaining digits in ascending order - since they were already in descending order, all you need to do is reverse them (save for digit-x, which can be placed in the correct place in O(n)).

An example will make this more clear:

123456784987654321
start with a number

123456784 987654321
^the first place from the right where the left-digit is less than the right

Digit "x" is 4
123456784 987654321
^find the smallest digit larger than 4 to the right
123456785 4 98764321
^place it to the left of 4
123456785 4 12346789
123456785123446789
^sort the digits to the right of 5.  Since all of them except
the '4' were already in descending order, all we need to do is
reverse their order, and find the correct place for the '4'

---

Proof of correctness:

Let's use capital letters to define digit-strings and lower-case for digits. The syntax AB means "the concatenation of strings A and B". < is lexicographical ordering, which is the same as integer ordering when the digit-strings are of equal length.

Our original number N is of the form AxB, where x is a single digit and B is sorted descending.
The number found by our algorithm is AyC, where y ∈ B is the smallest digit > x (it must exist due to the way x was chosen, see above), and C is sorted ascending.

Assume there is some number (using the same digits) N' such that AxB < N' < AyC. N' must begin with A or else it could not fall between them, so we can write it in the form AzD. Now our inequality is AxB < AzD < AyC, which is equivalent to xB < zD < yC where all three digit-strings contain the same digits.

In order for that to be true, we must have x <= z <= y. Since y is the smallest digit > x, z cannot be between them, so either z = x or z = y. Say z = x. Then our inequality is xB < xD < yC, which means B < D where both B and D have the same digits. However, B is sorted descending, so there is no string with those digits larger than it. Thus we cannot have B < D. Following the same steps, we see that if z = y, we cannot have D < C.

Therefore N' cannot exist, which means our algorithm correctly finds the next largest number.

An almost-identical problem appeared as a Code Jam problem and has a solution here:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

Here's a summary of the method using an example:

34722641

A. Split the sequence of digits in two, so that the right part is as long as possible while remaining in decreasing order:

34722 641

(If the entire number is in decreasing order, there's no bigger number to be made without adding digits.)

At this point, you know there is no larger number that starts with the left part, because the right part is already as large as possible with the leftover digits.

B.1. Select the last digit of the first sequence:

3472(2) 641

B.2. Find the smallest digit in the second sequence that is larger than it:

3472(2) 6(4)1

What you're doing is finding the smallest possible increase to the left part.

B.3. Swap them:

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

C. Sort the second sequence into increasing order:

34724 126

D. Done!

34724126

You split the number such that you knew there was no larger number with the same left part, you increased the left part by the smallest amount possible, and you made the remaining right part as small as possible, so you can be sure this new number is the smallest larger number that can be made with the same collection of digits.

Here's a compact (but partly brute force) solution in Python

def findnext(ii): return min(v for v in (int("".join(x)) for x in
    itertools.permutations(str(ii))) if v>ii)

In C++ you could make the permutations like this: https://stackoverflow.com/a/9243091/1149664 (It's the same algorithm as the one in itertools)

Here's an implementation of the top answer described by Weeble and BlueRaja, (other answers). I doubt there's anything better.

def findnext(ii):
    iis=list(map(int,str(ii)))
    for i in reversed(range(len(iis))):
        if i == 0: return ii
        if iis[i] > iis[i-1] :
            break        
    left,right=iis[:i],iis[i:]
    for k in reversed(range(len(right))):
        if right[k]>left[-1]:
           right[k],left[-1]=left[-1],right[k]
           break
    return int("".join(map(str,(left+sorted(right)))))

At minimum, here are a couple of example brute force String based solutions, that you should have been able to come up with right off the top of your head:

the list of digits in 38276 sorted is 23678

the list of digits in 38627 sorted is 23678

brute force increment, sort and compare

Along the brute force solutions would be convert to a String and brute force all the possible numbers using those digits.

Create ints out of them all, put them in a list and sort it, get the next entry after the target entry.

If you spent 30 minutes on this and didn't at least come up with at least a brute force approach, I wouldn't hire you either.

In the business world, a solution that is inelegant, slow and clunky but gets the job done is always more valuable than no solution at all, matter of fact that pretty much describes all business software, inelegant, slow and clunky.

function foo(num){
 sortOld = num.toString().split("").sort().join('');
 do{
    num++;
   sortNew = num.toString().split("").sort().join('');
 }while(sortNew!==sortOld);
 return num;
}

Your idea

> I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

is pretty good, actually. You just have to consider not only the last digit but all digits of less significance than the currently considered. Since before that is reached, we have a monotonic sequence of digits, that is the rightmost digit smaller than its right neighbour. Regard

1234675
    ^

The next larger number having the same digits is

1234756

The found digit is exchanged for the last digit - the smallest of the considered digits - and the remaining digits are arranged in increasing order.

I'm fairly sure your interviewer was trying to push you gently towards something like this:

local number = 564321;

function split(str)
    local t = {};
    for i = 1, string.len(str) do
        table.insert(t, str.sub(str,i,i));
    end
    return t;
end

local res = number;
local i = 1;
while number >= res do
    local t = split(tostring(res));
    if i == 1 then
        i = #t;
    end
    t[i], t[i-1] = t[i-1], t[i];
    i = i - 1;
    res = tonumber(table.concat(t));
end

print(res);

Not necessarily the most efficient or elegant solution but it solves the provided example in two cycles and swaps digits one at a time like he suggested.

Take a number and split it into digits. So if we have a 5 digit number, we have 5 digits: abcde

Now swap d and e and compare with the original number, if it is larger, you have your answer.

If it isn't larger, swap e and c. Now compare and if it is smaller swap d and e again (notice recursion), take smallest.

Carry on through until you find a larger number. With recursion it should work out as about 9 lines of scheme, or 20 of c#.

That is very interesting question.

Here is my java version. Take me about 3 hours from figuring out the pattern to completely finish the code before I checked other contributors' comments. Glad to see my idea is quite same with others.

O(n) solution. Honestly, I will fail this interview if the time is only 15 minutes and require complete code finish on white board.

Here are some points of interesting for my solution:

• Avoid any sorting .

• Avoid string operation completely

• Achieve O(logN) space complexity

I put detail comment in my code, and the Big O in each step.

  public int findNextBiggestNumber(int input  )   {
    //take 1358642 as input for example.
    //Step 1: split the whole number to a list for individual digital   1358642->[2,4,6,8,5,3,1]
    // this step is O(n)
    int digitalLevel=input;

    List<Integer> orgNumbersList=new ArrayList<Integer>()   ;

    do {
        Integer nInt = new Integer(digitalLevel % 10);
        orgNumbersList.add(nInt);

        digitalLevel=(int) (digitalLevel/10  )  ;


    } while( digitalLevel >0)    ;
    int len= orgNumbersList.size();
    int [] orgNumbers=new int[len]  ;
    for(int i=0;i<len;i++){
        orgNumbers[i ]  =  orgNumbersList.get(i).intValue();
    }
    //step 2 find the first digital less than the digital right to it
    // this step is O(n)


    int firstLessPointer=1;
    while(firstLessPointer<len&&(orgNumbers[firstLessPointer]>orgNumbers[ firstLessPointer-1 ])){
        firstLessPointer++;
    }
     if(firstLessPointer==len-1&&orgNumbers[len-1]>=orgNumbers[len-2]){
         //all number is in sorted order like 4321, no answer for it, return original
         return input;
     }

    //when step 2 step finished, firstLessPointer  pointing to number 5

     //step 3 fristLessPointer found, need to find  to  first number less than it  from low digital in the number
    //This step is O(n)
    int justBiggerPointer=  0 ;

    while(justBiggerPointer<firstLessPointer&& orgNumbers[justBiggerPointer]<orgNumbers[firstLessPointer]){
        justBiggerPointer++;
    }
    //when step 3 finished, justBiggerPointer  pointing to 6

    //step 4 swap the elements  of justBiggerPointer and firstLessPointer .
    // This  is O(1) operation   for swap

   int tmp=  orgNumbers[firstLessPointer] ;

    orgNumbers[firstLessPointer]=  orgNumbers[justBiggerPointer]  ;
     orgNumbers[justBiggerPointer]=tmp ;


     // when step 4 finished, the list looks like        [2,4,5,8,6,3,1]    the digital in the list before
     // firstLessPointer is already sorted in our previous operation
     // we can return result from this list  but  in a differrent way
    int result=0;
    int i=0;
    int lowPointer=firstLessPointer;
    //the following pick number from list from  the position just before firstLessPointer, here is 8 -> 5 -> 4 -> 2
    //This Operation is O(n)
    while(lowPointer>0)        {
        result+= orgNumbers[--lowPointer]* Math.pow(10,i);
        i++;
    }
    //the following pick number from list   from position firstLessPointer
    //This Operation is O(n)
    while(firstLessPointer<len)        {
        result+= orgNumbers[firstLessPointer++ ]* Math.pow(10,i);
        i++;
    }
     return  result;

}

Here is result running in Intellj:

959879532-->959892357
1358642-->1362458
1234567-->1234576
77654321-->77654321
38276-->38627
47-->74

A javascript implementation of @BlueRaja's algorithm.

var Bar = function(num){ 
  num = num.toString();
  var max = 0;
  for(var i=num.length-2; i>0; i--){
    var numArray = num.substr(i).split("");
    max = Math.max.apply(Math,numArray);
    if(numArray[0]<max){
        numArray.sort(function(a,b){return a-b;});
        numArray.splice(-1);
        numArray = numArray.join("");
        return Number(num.substr(0,i)+max+numArray);
    }
  }
  return -1;
};

PHP Code

function NextHigherNumber($num1){
$num = strval($num1);
$max = 0;
for($i=(strlen($num)-2); $i>=0; $i--){
	$numArrayRaw = substr($num, $i);
	$numArray = str_split($numArrayRaw);
	$max = max($numArray);
	if ($numArray[0] < $max){
		sort( $numArray, SORT_NUMERIC );
		array_pop($numArray);
		$numarrstr = implode("",$numArray);
		$rt = substr($num,0,$i) . $max . $numarrstr;
		return $rt;
	}
}
return "-1";
}
echo NextHigherNumber(123);

A solution (in Java) could be the following (I am sure friends here can find a better):
Start swapping digits from the end of the string until you get a higher number.
I.e. first start moving up the lower digit.Then the next higher etc until you hit the next higher.
Then sort the rest. In your example you would get:

38276 --> 38267 (smaller) --> 38627 Found it    
    ^        ^                  ^        

 public static int nextDigit(int number){
	String num = String.valueOf(number);		
	int stop = 0;		
	char [] chars = null;
	outer:
		for(int i = num.length() - 1; i > 0; i--){			
			chars = num.toCharArray();
			for(int j = i; j > 0; j--){
				char temp = chars[j];
				chars[j] = chars[j - 1];
				chars[j - 1] = temp;
				if(Integer.valueOf(new String(chars)) > number){
					stop = j;					
					break outer;								
				}				
			}				
		}
		
	Arrays.sort(chars, stop, chars.length);	
	return Integer.valueOf(new String(chars));
}

If you are programming in C++, you could use next_permutation:

#include <algorithm>
#include <string>
#include <iostream>

int main(int argc, char **argv) {
  using namespace std; 
   string x;
   while (cin >> x) {
    cout << x << " -> ";
    next_permutation(x.begin(),x.end());
    cout << x << "\n";
  }
  return 0;
}

I didn't know anything about the brute force algorithm when answering this question, so I approached it from another angle. I decided to search the entire range of possible solutions that this number could possibly be rearranged into, starting from the number_given+1 up to the max number available (999 for a 3 digit number, 9999 for 4 digits, etc.). I did this kind of like finding a palindrome with words, by sorting the numbers of each solution and comparing it to the sorted number given as the parameter. I then simply returned the first solution in the array of solutions, as this would be the next possible value.

Here is my code in Ruby:

def PermutationStep(num)
  
    a = []
    (num.to_s.length).times { a.push("9") }
    max_num = a.join('').to_i
    verify = num.to_s.split('').sort
    matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }

    if matches.length < 1
      return -1
    else
      matches[0]
    end
end

I've only tested this with two numbers. They worked. As IT Manager for 8 years until retiring last December, I cared about three things:

1. Accuracy: it's good if it works - always.
2. Speed: has to be acceptable to the user.
3. Clarity: I'm probably not as smart as you are, but I'm paying you. Make sure you explain what you're doing, in English.

Omar, best of luck going forward.

Sub Main()

Dim Base(0 To 9) As Long
Dim Test(0 To 9) As Long

Dim i As Long
Dim j As Long
Dim k As Long
Dim ctr As Long

Const x As Long = 776914648
Dim y As Long
Dim z As Long

Dim flag As Boolean

' Store the digit count for the original number in the Base vector.
    For i = 0 To 9
        ctr = 0
        For j = 1 To Len(CStr(x))
            If Mid$(CStr(x), j, 1) = i Then ctr = ctr + 1
        Next j
        Base(i) = ctr
    Next i
    
' Start comparing from the next highest number.
    y = x + 1
    Do
    
' Store the digit count for the each new number in the Test vector.
        flag = False
        For i = 0 To 9
            ctr = 0
            For j = 1 To Len(CStr(y))
                If Mid$(CStr(y), j, 1) = i Then ctr = ctr + 1
            Next j
            Test(i) = ctr
        Next i
        
' Compare the digit counts.
        For k = 0 To 9
            If Test(k) <> Base(k) Then flag = True
        Next k
        
' If no match, INC and repeat.
        If flag = True Then
            y = y + 1
            Erase Test()
        Else
            z = y ' Match.
        End If
       
    Loop Until z > 0
    
    MsgBox (z), , "Solution"

End Sub

For a nice write-up of how to do this, see "Algorithm L" in Knuth's "The Art of Computer Programming: Generating all Permutations" (.ps.gz).

Here is my code, it's a modified version of this example

Library:

class NumPermExample
{
	// print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s, ArrayList<String> perm)
	{
		perm1("", s);
	}

    private static void perm1(String prefix, String s, ArrayList<String> perm)
	{
        int N = s.length();
        if (N == 0)
		{
			System.out.println(prefix);
			perm.add(prefix);
		}
        else
		{
            for (int i = 0; i < N; i++)
                perm1(prefix + s.charAt(i), s.substring(0, i)
                    + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s, ArrayList<String> perm)
	{
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n, ArrayList<String> perm)
	{
        if (n == 1)
		{
            System.out.println(a);
			perm.add(new String(a));
            return;
        }
        
        for (int i = 0; i < n; i++)
		{
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j)
	{
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

	// next higher permutation
	public static int nextPermutation (int number)
	{
		ArrayList<String> perm = new ArrayList<String>();
		
		String cur = ""+number;

		int nextPerm = 0;

		perm1(cur, perm);

		for (String s : perm)
		{
			if (Integer.parseInt(s) > number
                        && (nextPerm == 0 ||
                            Integer.parseInt(s) < nextPerm))
			{
				nextPerm = Integer.parseInt(s);
			}
		}

            return nextPerm;
	}
}

Test:

public static void main(String[] args) 
{
	int a = 38276;
    
	int b = NumPermExample.nextPermutation(a);
	
    System.out.println("a: "+a+", b: "+b);
}

Add 9 to the given n digit number. Then check if it is within the limit(the first (n+1) digit number). If it is then check if the digits in the new number are the same as the digits in the original number. Repeat adding 9 until both the conditions are true. Stop the algo when the number goes beyond the limit.

I could not come up with a contradicting test case for this method.

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<string.h>
#include<sstream>
#include<iostream>

using namespace std;
int compare (const void * a, const void * b)
{
    return *(char*)a-*(char*)b;
}

/*-----------------------------------------------*/

int main()
{
    char number[200],temp;
    cout<<"please enter your number?"<<endl;
    gets(number);
    int n=strlen(number),length;
    length=n;
    while(--n>0)
    {
        if(number[n-1]<number[n])
        {
            for(int i=length-1;i>=n;i--)
            {
                if(number[i]>number[n-1])
                {
                    temp=number[i];
                    number[i]=number[n-1];
                    number[n-1]=temp;
                    break;
                }
            }
            qsort(number+n,length-n,sizeof(char),compare);
            puts(number); 
            return 0;
        }
    }
    cout<<"sorry itz the greatest one :)"<<endl;
}

Just another solution using python:

def PermutationStep(num):
    if sorted(list(str(num)), reverse=True) == list(str(num)):
        return -1
    ls = list(str(num))
    n = 0
    inx = 0
    for ind, i in enumerate(ls[::-1]):
        if i < n:
            n = i
            inx = -(ind + 1)
            break
        n = i
    ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]

    nl = ls[inx::-1][::-1]
    ln = sorted(ls[inx+1:])
    return ''.join(nl) + ''.join(ln)

print PermutationStep(23514)

Output:

23541

public static void findNext(long number){

        /* convert long to string builder */    

		StringBuilder s = new StringBuilder();
		s.append(number);
		int N = s.length();
		int index=-1,pivot=-1;

/* from tens position find the number (called pivot) less than the number in right */ 

		for(int i=N-2;i>=0;i--){
			
             int a = s.charAt(i)-'0';
		     int b = s.charAt(i+1)-'0';
			
             if(a<b){
				pivot = a;
				index =i;
				break;
			}
		}

      /* if no such pivot then no solution */   

		if(pivot==-1) System.out.println(" No such number ")
			
		else{	

     /* find the minimum highest number to the right higher than the pivot */

			int nextHighest=Integer.MAX_VALUE, swapIndex=-1;

			for(int i=index+1;i<N;i++){

			int a = s.charAt(i)-'0';

			if(a>pivot && a<nextHighest){
					nextHighest = a;
					swapIndex=i;
				}
			}
              

     /* swap the pivot and next highest number */

			s.replace(index,index+1,""+nextHighest);
			s.replace(swapIndex,swapIndex+1,""+pivot);

/* sort everything to right of pivot and replace the sorted answer to right of pivot */

 			char [] sort = s.substring(index+1).toCharArray();
			Arrays.sort(sort);

			s.replace(index+1,N,String.copyValueOf(sort));

			System.out.println("next highest number is "+s);
		}
		
	}

Below is the code to generate all permutations of a number .. though one has to convert that integer to string using String.valueOf(integer) first.

/**
 * 
 * Inserts a integer at any index around string.
 * 
 * @param number
 * @param position
 * @param item
 * @return
 */
public String insertToNumberStringAtPosition(String number, int position,
		int item) {
	String temp = null;
	if (position >= number.length()) {
		temp = number + item;
	} else {
		temp = number.substring(0, position) + item
				+ number.substring(position, number.length());
	}
	return temp;
}

/**
 * To generate permutations of a number.
 * 
 * @param number
 * @return
 */
public List<String> permuteNumber(String number) {
	List<String> permutations = new ArrayList<String>();
	if (number.length() == 1) {
		permutations.add(number);
		return permutations;
	}
	// else
	int inserterDig = (int) (number.charAt(0) - '0');
	Iterator<String> iterator = permuteNumber(number.substring(1))
			.iterator();
	while (iterator.hasNext()) {
		String subPerm = iterator.next();
		for (int dig = 0; dig <= subPerm.length(); dig++) {
			permutations.add(insertToNumberStringAtPosition(subPerm, dig,
					inserterDig));
		}
	}
	return permutations;
}

#include<bits/stdc++.h>
using namespace std;
int main() 
{
	int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
	char temp[100],a[100]`enter code here`,n;
	min=9999;
	//cout<<"Enter the number\n";
	cin>>a;
	len=strlen(a);
	for(i=0;i<len;i++)
	{
		if(a[i]<a[i+1]){flag=1;break;}
	}
	if(flag==0){cout<<a<<endl;}
	else
	{
		for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
		for(k=0;k<i-1;k++)cout<<a[k];
		for(j=i;j<len;j++)
		{
			if(((int)a[j]-48)-((int)a[i-1]-48)>0)
			{
				diff=((int)a[j]-48)-((int)a[i-1]-48);
				if(diff<min){n=a[j];min=diff;}
			}
		}
		cout<<n;
		for(z=i-1;z<len;z++)
		{
			temp[u]=a[z];
			u++;
		}
		temp[u]='\0';
		sort(temp,temp+strlen(temp));
		for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
	}
	return 0;
}

Here is my implementation of it in Ruby:

def foo num  
  num = num.to_s.chars.map(&:to_i)
  return num.join.to_i if num.size < 2
  for left in (num.size-2).downto(0) do
    for right in (num.size-1).downto(left+1) do
      if num[right]>num[left]
        num[left],num[right] = num[right],num[left]        
        return (num[0..left] + num[left+1..num.size-1].sort).join.to_i
      end
    end
  end
  return num.join.to_i
end

p foo 38276 
#will print: 38627

Yet another Java implementation, runnable out of the box and completed with tests. This solution is O(n) space and time using good old dynamic programming.

If one wants to bruteforce, there are 2 kinds of bruteforce:

1. Permute all the things, then pick min higher: O(n!)

2. Similar to this implementation, but instead of DP, bruteforcing the step of populating the indexToIndexOfNextSmallerLeft map will run in O(n^2).

---

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NextHigherSameDigits {

	public long next(final long num) {
		final char[] chars = String.valueOf(num).toCharArray();
		final int[] digits = new int[chars.length];
		for (int i = 0; i < chars.length; i++) {
			digits[i] = Character.getNumericValue(chars[i]);
		}

		final Map<Integer, Integer> indexToIndexOfNextSmallerLeft = new HashMap<>();
		indexToIndexOfNextSmallerLeft.put(1, digits[1] > digits[0] ? 0 : null);
		for (int i = 2; i < digits.length; i++) {
			final int left = digits[i - 1];
			final int current = digits[i];
			Integer indexOfNextSmallerLeft = null;
			if (current > left) {
				indexOfNextSmallerLeft = i - 1;
			} else {
				final Integer indexOfnextSmallerLeftOfLeft = indexToIndexOfNextSmallerLeft.get(i - 1);
				final Integer nextSmallerLeftOfLeft = indexOfnextSmallerLeftOfLeft == null ? null : 
					digits[indexOfnextSmallerLeftOfLeft];

				if (nextSmallerLeftOfLeft != null && current > nextSmallerLeftOfLeft) {
					indexOfNextSmallerLeft = indexOfnextSmallerLeftOfLeft;
				} else {
					indexOfNextSmallerLeft = null;
				}
			}

			indexToIndexOfNextSmallerLeft.put(i, indexOfNextSmallerLeft);
		}

		Integer maxOfindexOfNextSmallerLeft = null;
		Integer indexOfMinToSwapWithNextSmallerLeft = null;
		for (int i = digits.length - 1; i >= 1; i--) {
			final Integer indexOfNextSmallerLeft = indexToIndexOfNextSmallerLeft.get(i);
			if (maxOfindexOfNextSmallerLeft == null ||
					(indexOfNextSmallerLeft != null && indexOfNextSmallerLeft > maxOfindexOfNextSmallerLeft)) {

				maxOfindexOfNextSmallerLeft = indexOfNextSmallerLeft;
				if (maxOfindexOfNextSmallerLeft != null && (indexOfMinToSwapWithNextSmallerLeft == null || 
						digits[i] < digits[indexOfMinToSwapWithNextSmallerLeft])) {
					
					indexOfMinToSwapWithNextSmallerLeft = i;
				}
			}
		}

		if (maxOfindexOfNextSmallerLeft == null) {
			return -1;
		} else {
			swap(digits, indexOfMinToSwapWithNextSmallerLeft, maxOfindexOfNextSmallerLeft);
			reverseRemainingOfArray(digits, maxOfindexOfNextSmallerLeft + 1);
			return backToLong(digits);
		}
	}

	private void reverseRemainingOfArray(final int[] digits, final int startIndex) {
		final int[] tail = Arrays.copyOfRange(digits, startIndex, digits.length);
		for (int i = tail.length - 1; i >= 0; i--) {
			digits[(digits.length - 1)  - i] = tail[i];					
		}
	}

	private void swap(final int[] digits, final int currentIndex, final int indexOfNextSmallerLeft) {
		int temp = digits[currentIndex];
		digits[currentIndex] = digits[indexOfNextSmallerLeft];
		digits[indexOfNextSmallerLeft] = temp;
	}

	private long backToLong(int[] digits) {		
		StringBuilder sb = new StringBuilder();
		for (long i : digits) {
			sb.append(String.valueOf(i));
		}

		return Long.parseLong(sb.toString());
	}

	@Test
	public void test() {
		final long input1 =    34722641;
		final long expected1 = 34724126;
		final long output1 = new NextHigherSameDigits().next(input1);
		assertEquals(expected1, output1);
	
		final long input2 =    38276;
		final long expected2 = 38627;
		final long output2 = new NextHigherSameDigits().next(input2);
		assertEquals(expected2, output2);
		
		final long input3 =    54321;
		final long expected3 = -1;
		final long output3 = new NextHigherSameDigits().next(input3);
		assertEquals(expected3, output3);
		
		final long input4 =    123456784987654321L;
		final long expected4 = 123456785123446789L;
		final long output4 = new NextHigherSameDigits().next(input4);
		assertEquals(expected4, output4);
		
		final long input5 =    9999;
		final long expected5 = -1;
		final long output5 = new NextHigherSameDigits().next(input5);
		assertEquals(expected5, output5);
	}

}

We need to find the right most bit 0 followed by a 1 and flip this right most 0 bit to a 1.

for example lets say our input is 487, which is 111100111 in binary.

we flip the right most 0 that has 1 following it

so we get 111101111

but now we have a extra 1 and one less 0, so we reduce the number of 1's on the right of the flip bit by 1 and increase the no of 0 bits by 1, yielding

111101011 - binary 491

int getNextNumber(int input)
{
	int flipPosition=0;
	int trailingZeros=0;
	int trailingOnes=0;
	int copy = input;

	//count trailing zeros
	while(copy != 0 && (copy&1) == 0 )
	{
		++trailingZeros;

		//test next bit
		copy = copy >> 1;
	}

	//count trailing ones
	while(copy != 0 && (copy&1) == 1 )
	{
		++trailingOnes;

		//test next bit
		copy = copy >> 1;
	}

	//if we have no 1's (i.e input is 0) we cannot form another pattern with 
	//the same number of 1's which will increment the input, or if we have leading consecutive
	//ones followed by consecutive 0's up to the maximum bit size of a int
	//we cannot increase the input whilst preserving the original no of 0's and
	//1's in the bit pattern
	if(trailingZeros + trailingOnes  == 0 || trailingZeros + trailingOnes == 31)
		return -1;

	//flip first 0 followed by a 1 found from the right of the bit pattern
	flipPosition = trailingZeros + trailingOnes+1;
	input |= 1<<(trailingZeros+trailingOnes);

	//clear fields to the right of the flip position
	int mask = ~0 << (trailingZeros+trailingOnes);
	input &= mask;

	//insert a bit pattern to the right of the flip position that will contain
	//one less 1 to compensate for the bit we switched from 0 to 1
	int insert = flipPosition-1;
	input |= insert;

	return input;
}

int t,k,num3,num5;
scanf("%d",&t);
int num[t];
for(int i=0;i<t;i++){
    scanf("%d",&num[i]);   
}
for(int i=0;i<t;i++){
    k=(((num[i]-1)/3)+1); 
    if(k<0)
        printf("-1");
    else if(num[i]<3 || num[i]==4 || num[i]==7)
        printf("-1");
    else{
        num3=3*(2*num[i] - 5*k);
        num5=5*(3*k -num[i]);
        for(int j=0;j<num3;j++)
            printf("5");
        for(int j=0;j<num5;j++)
            printf("3");
    }
    printf("\n");
}

Here is the Java Implementation

public static int nextHigherNumber(int number) {
	Integer[] array = convertToArray(number);
	int pivotIndex = pivotMaxIndex(array);
	int digitInFirstSequence = pivotIndex -1;
	int lowerDigitIndexInSecondSequence = lowerDigitIndex(array[digitInFirstSequence], array, pivotIndex);
	swap(array, digitInFirstSequence, lowerDigitIndexInSecondSequence);
	doRercursiveQuickSort(array, pivotIndex, array.length - 1);
	return arrayToInteger(array);
}

public static Integer[] convertToArray(int number) {
    int i = 0;
    int length = (int) Math.log10(number);
    int divisor = (int) Math.pow(10, length);
    Integer temp[] = new Integer[length + 1];

    while (number != 0) {
        temp[i] = number / divisor;
        if (i < length) {
            ++i;
        }
        number = number % divisor;
        if (i != 0) {
            divisor = divisor / 10;
        }
    }
    return temp;
}

private static int pivotMaxIndex(Integer[] array) {
	int index = array.length - 1;
	while(index > 0) {
		if (array[index-1] < array[index]) {
			break;
		}
		index--;
	}		
	return index;
}

private static int lowerDigitIndex(int number, Integer[] array, int fromIndex) {
	int lowerMaxIndex = fromIndex;
	int lowerMax = array[lowerMaxIndex];
	while (fromIndex < array.length - 1) {
		if (array[fromIndex]> number && lowerMax > array[fromIndex]) {
			lowerMaxIndex = fromIndex; 
		}
		fromIndex ++;
	}
	return lowerMaxIndex;
}

public static int arrayToInteger(Integer[] array) {
	int number = 0;
	for (int i = 0; i < array.length; i++) {
		number+=array[i] * Math.pow(10, array.length-1-i);
	}
	return number;
}

Here is the Unit Tests

@Test
public void nextHigherNumberTest() {
	assertThat(ArrayUtils.nextHigherNumber(34722641), is(34724126));
	assertThat(ArrayUtils.nextHigherNumber(123), is(132));
}

I know this is very old question but still I didn't find easy code in c#. This might help guys who are attending interviews.

class Program
{
    static void Main(string[] args)
    {

        int inputNumber = 629;
        int i, currentIndexOfNewArray = 0;

        int[] arrayOfInput = GetIntArray(inputNumber);
        var numList = arrayOfInput.ToList();

        int[] newArray = new int[arrayOfInput.Length];

        do
        {
            int temp = 0;
            int digitFoundAt = 0;
            for (i = numList.Count; i > 0; i--)
            {
                if (numList[i - 1] > temp)
                {
                    temp = numList[i - 1];
                    digitFoundAt = i - 1;
                }
            }
            
            newArray[currentIndexOfNewArray] = temp;
            currentIndexOfNewArray++;
            numList.RemoveAt(digitFoundAt);
        } while (arrayOfInput.Length > currentIndexOfNewArray);

        

        Console.WriteLine(GetWholeNumber(newArray));

        Console.ReadKey();

        
    }

    public static int[] GetIntArray(int num)
    {
        IList<int> listOfInts = new List<int>();
        while (num > 0)
        {
            listOfInts.Add(num % 10);
            num = num / 10;
        }
        listOfInts.Reverse();
        return listOfInts.ToArray();
    }

    public static double GetWholeNumber(int[] arrayNumber)
    {
        double result = 0;
        double multiplier = 0;
        var length = arrayNumber.Count() - 1;
        for(int i = 0; i < arrayNumber.Count(); i++)
        {
            multiplier = Math.Pow(10.0, Convert.ToDouble(length));
            result += (arrayNumber[i] * multiplier);
            length = length - 1;
        }

        return result;
    }
}

Very simple implementation using Javascript, next highest number with same digits

/*
Algorithm applied
I) Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.

II) Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.

III) Swap the above found two digits, we get 536974 in above example.

IV) Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

*/

function findNext(arr)
{
  let i;
  //breaking down a digit into arrays of string and then converting back that array to number array
  let arr1=arr.toString().split('').map(Number) ;
  //started to loop from the end of array 
  for(i=arr1.length;i>0;i--)
  {
  	//looking for if the current number is greater than the number next to it
    if(arr1[i]>arr1[i-1])
    {// if yes then we break the loop it so that we can swap and sort
      break;}
  }
  
  if(i==0)
  {console.log("Not possible");}

   else
  {
   //saving that big number and smaller number to the left of it
   let smlNum =arr1[i-1];
    let bigNum =i;
   /*now looping again and checking if we have any other greater number, if we have one AFTER big number and smaller number to the right. 
     A greater number that is of course greater than that smaller number but smaller than the first number we found.
     Why are doing this? Because that is an algorithm to find next higher number with same digits. 
   */
    for(let j=i+1;j<arr1.length;j++)
      {//What if there are no digits afters those found numbers then of course loop will not be initiated otherwise...
        if(arr1[j]> smlNum && arr1[j]<arr1[i])
        {// we assign that other found number here and replace it with the one we found before
          bigNum=j;
          
        }
      } //now we are doing swapping of places the small num and big number , 3rd part of alogorithm
    arr1[i-1]=arr1[bigNum];
          arr1[bigNum]=smlNum;
    //returning array 
    //too many functions applied sounds complicated right but no, here is the  trick
    //return arr first then apply each function one by one to see output and then further another func to that output to match your needs
    // so here after swapping , 4th part of alogorithm is to sort the array right after the 1st small num we found
    // to do that first we simple take part of array, we splice it and then we apply sort fucntion, then check output (to check outputs, pls use chrome dev console)
    //and then  simply the rest concat and join to main one digit again.
     return arr1.concat((arr1.splice(i,arr1.length)).sort(function(a, b){return a-b})).join('');
    

  
    // Sorry to make it too long but its fun explaining things in much easier ways as much as possible!!
  }
  
}


findNext(1234);

Since there are lot of comments, so it's better you can copy it to your text editor. Thanks!

There are lots of good answers but I didn't find a decent Java implementation. Here is my two cents:

public void findNext(int[] nums) {
    int i = nums.length - 1;
    // nums[i - 1] will be the first non increasing number
    while (i > 0 && nums[i] <= nums[i - 1]) {
        i--;
    }
    if (i == 0) {
        System.out.println("it has been the greatest already");
    } else {
        // Find the smallest digit in the second sequence that is larger than it:
        int j = nums.length - 1;
        while (j >= 0 && nums[j] < nums[i - 1]) {
            j--;
        }
        swap(nums, i - 1, j);
        Arrays.sort(nums, i, nums.length);
        System.out.println(Arrays.toString(nums));
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

This is a more compact answer in Java to this algorithm than this

   public static int permutate2(int number){
        String[] numArray = String.valueOf(number).split("");

        for(int i = numArray.length - 1; i > 0; i--){
            int current = Integer.valueOf(numArray[i]);
            int previous = Integer.valueOf(numArray[i - 1]);

            if(previous < current){
                String[] rest = String.valueOf(number).substring(i, numArray.length).split("");
                Arrays.sort(rest);

                String picker = rest[0];
                int pickerIndex = 0;
                for(int n = 0; n < rest.length ; n++){
                    if(Integer.valueOf(rest[n]) > previous){
                        picker = rest[n];
                        pickerIndex = n;
                        break;
                    }
                }
                numArray[i - 1] = picker;
                rest[pickerIndex] = String.valueOf(previous);
                Arrays.sort(rest);

                String newNumber = "";
                for(int z = 0; z <= i - 1; z++){
                    newNumber += numArray[z];
                }
                for(String z : rest){
                    newNumber += z;
                }

                return Integer.valueOf(newNumber);
            }
        }

        return number;
   }

Heres a clever solution I did not come up with in C#

 using System;
using System.Linq;

 public static long NextBiggerNumber(long n)
    {        
       String str = GetNumbers(n);
        for (long i = n+1; i <= long.Parse(str); i++)
        {
            if(GetNumbers(n)==GetNumbers(i))
            {
                return i;
            }
        }
        return -1;        
    }
    public static string GetNumbers(long number)
    {
      return string.Join("", number.ToString().ToCharArray().OrderByDescending(x => x));
    }

Ruby Solution

def next_bigger(num)
  char_array = num.to_s.split('')
  return -1 if char_array.uniq.size == 1

  arr, target_idx, target_char = [], nil, nil
  # get first left-digit less than the right from right side
  (char_array.count - 1).times do |i|
    arr.unshift(char_array[-(i+1)])

    if char_array[-(i+2)] < char_array[-(i+1)]
      target_idx = char_array.count - (i + 2)
      target_char = char_array[-(i+2)]
      arr.unshift(char_array[-(i+2)])
      break
    end
  end
  return -1 unless target_idx

  # first smallest digit larger than target_char to the right
  ((target_char.to_i + 1)..9).to_a.each do |ch|
    if arr.index(ch.to_s)
      flip_char = arr.delete_at(arr.index(ch.to_s))
      # sort the digits to the right of flip_char
      arr.sort!
      # place flip_char to the left of target_char
      arr.unshift(flip_char)
      break
    end
  end

  (char_array[0...target_idx] + arr).join().to_i
end

Implementation in PHP

Time complexity O(n)

$n = "9875";
$n_size = strlen($n);
for($i = $n_size-1; $i > 0; $i-- ) {
	 if($n[$i] > $n[$i-1]){
     $temp = $n[$i];
     $n[$i] = $n[$i-1];
     $n[$i-1] = $temp;
     break;
     }
    
}

if($i == 0){
	echo "Next Greater value no possible";
}else{
	echo $n;
}

 private static int GetNextHigherNumber(int num)
        {
            //given 38276 return 38627

            string numberstring = num.ToString();

            char[] sNum = numberstring.ToCharArray();

            for (int i = sNum.Length - 1; i > 0; i--)
            {
                for (int j = i - 1; j > 0; j--)
                {
                    if (sNum[i] > sNum[j])
                    {
                        for (int x = i; x > j; x--)
                        {
                            char chr = sNum[x]; 
                            sNum[x] = sNum[x - 1];
                            sNum[x - 1] = chr;
                        }

                        i = 0;
                        break;
                    }
                }
            }

            numberstring = string.Empty;
            for(int x= 0 ; x<sNum.Length;x++)
            {
                numberstring += sNum[x].ToString();
            }

            return Convert.ToInt32(numberstring);
        }

Answer in java with one more condition added

• Next number should also be an Even number

    public static int nextDigit(int number) {
   String num = String.valueOf(number);
   int stop = 0;
   char[] orig_chars = null;
   char[] part1 = null;
   char[] part2 = null;
   orig_chars = num.toCharArray();
           
   System.out.println("vivek c r");
   for (int i = orig_chars.length - 1; i > 0; i--) {
   	String previous = orig_chars[i - 1] + "";
   	String next = orig_chars[i] + "";
   	if (Integer.parseInt(previous) < Integer.parseInt(next))
  
   	{
   		if (Integer.parseInt(previous) % 2 == 0) {
  
   			String partString1 = "";
   			String partString2 = "";
   			for (int j = 0; j <= i - 1; j++) {
   				partString1 = partString1.concat(orig_chars[j] + "");
   			}
   			part1 = partString1.toCharArray();
   			for (int k = i; k < orig_chars.length; k++) {
   				partString2 = partString2.concat(orig_chars[k] + "");
   			}
   			part2 = partString2.toCharArray();
   			Arrays.sort(part2);
   			for (int l = 0; l < part2.length; l++) {
   				char temp = '0';
   				if (part2[l] > part1[i - 1]) {
   					temp = part1[i - 1];
   					part1[i - 1] = part2[l];
   					part2[l] = temp;
   					break;
   				}
   			}
   			for (int m = 0; m < part2.length; m++) {
   				char replace = '0';
   				if (part2[m] % 2 == 0) {
   					replace = part2[m];
   					for (int n = m; n < part2.length - 1; n++) {
   						part2[n] = part2[n + 1];
   					}
   					part2[part2.length - 1] = replace;
   					break;
   				}
   			}
  
   			System.out.print(part1);
   			System.out.println(part2);
   			System.exit(0);
   		}
   	}
   }
   System.out.println("NONE");
   
   return 0;
           }
  

#include <iostream>
using namespace std;

int main ()
{
  int num=15432;
  int quot,rem;
  int numarr[5];
  int length=0;
  while(num!=0)
  {
      rem=num%10;
      num = num/10;
      numarr[length]=rem;
      length++;
  }

 for(int j=0;j<length;j++)
  {
  for(int i=0;i<length;i++)
  {
      if(numarr[i]<numarr[i+1])
      {
          int tmp=numarr[i];
          numarr[i]=numarr[i+1];
          numarr[i+1]=tmp;
      }
  }
  }
  
  for(int j=0;j<length;j++)
  {
   cout<<numarr[j];
  }
  return 0;
}

import java.util.Scanner;
public class Big {

	public static void main(String[] args) {
	
		
		Scanner sc = new Scanner(System.in);
		System.out.print("Enter the number ");
		String str = sc.next();
		int t=0;
		
		char[] chars  = str.toCharArray();
		
		
		
		for(int i=str.length()-1,j=str.length()-2;j>=0;j--)
		{
			
			
				if((int)chars[i]>(int)chars[j])
				{
					t = (int)chars[i];
					chars[i] = chars[j];
					chars[j]=(char)t;
					
					for(int k=j+1;k<str.length()-1;k++)
					{
						for(int l=k+1;l<str.length();l++)
						{
							if(chars[k]>chars[l])
							{
								int m = (int)chars[k];
								chars[k] = chars[l];
								chars[l]=(char)m;
							}
						}
					}
					
					break;
				}
				
				
			
			
			
			
		}
		System.out.print("The next Big number is: ");
		
		for(int i=0;i<str.length();i++){
			System.out.print(chars[i]);
		}
		sc.close();
	}
	

}