Next Higher Number

Given an integer, find the next higher number with the same digits. If the number is the largest number that can be formed from the given digits, then print None.
Example:
Input:
32841
Output:
34128

Input:
98765
Output:
None


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

1. Start scanning from the right.
2. Find a digit D1 which is not in ascending order from right.
3. If all the digits from right to left are ascending then print "None".
4. Find a digit D2 which is right of D1, such that it is the smallest number greater than D1.
5. Swap D1 and D2.
6. Now sort the digits right of D1's original position.

Please watch the video for detailed explanation.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.virendra;

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

/**
 * <b>IDeserve <br/>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a> <br/>
 * Given an integer, find the next higher number with the same digits.
 * 
 * @author Virendra
 */
public class NextHigherNumber {

	public static void nextHigherNumber(Integer num) {
		Integer temp = num;
		ArrayList<Integer> digits = new ArrayList<Integer>();

		while (temp > 0) {
			int digit = temp % 10;
			temp = temp / 10;
			digits.add(digit);
		}

		int j = 0;
		int i = j + 1;

		if (digits.size() > 1) {

			while (i < digits.size()) {
				if (digits.get(i) < digits.get(j)) {
					break;
				}
				j++;
				i++;
			}

			if (i >= digits.size()) {
				System.out.println("None");
				return;
			}

			// where to swap
			j = 0;

			while (j < i) {
				if (digits.get(j) > digits.get(i))
					break;
				j++;
			}
			// swap last and i
			int dg = digits.get(i);
			digits.set(i, digits.get(j));
			digits.set(j, dg);
		} else {
			System.out.println("None");
			return;
		}

		List<Integer> subList = digits.subList(0, i);
		Collections.sort(subList);
		int m = digits.size() - 1;
		while (m >= i) {
			System.out.print(digits.get(m));
			m--;
		}

		m = 0;
		while (m < subList.size()) {
			System.out.print(subList.get(m));
			m++;
		}

		System.out.println();

	}

	public static void main(String args[]) {
		nextHigherNumber(12543);
		nextHigherNumber(4132);
		nextHigherNumber(1234);
		nextHigherNumber(32841);
		nextHigherNumber(30102);
		nextHigherNumber(98765);
	}
}
		

Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer