Saturday, July 30, 2016

Next greater number with same digits

Given an integer number, find out next greater number formed with same digits.

Approach 1: 
If we carefully look at integer numbers, if all the digits are sorted in ascending order then it's the lowest number you can get with same digits. If we descending sort all the numbers then we will get the greatest number which can be formed with same digits.
So in order to generate the required number start from rightmost digit, check where any of the digits is less than the digit in right, if yes then mark that position.
Now sort all the digits in right from that position, and replace that digit with a greater digit in the sorted list.

The solution below implements this approach.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NextNumberWithSameDigits {
    public static void main(String[] args) {
        int number = 12;

        List integerList = ConvertToArray(number);
        int swapIndex = 1;
        while (swapIndex < integerList.size() && integerList.get(swapIndex-1) <= integerList.get(swapIndex)){
            swapIndex++;
        }

        if (swapIndex == integerList.size()){
            System.out.println("No next greater number can be formed");
            return;
        }

        Integer value = integerList.get(swapIndex);

        List copyList = integerList.subList(0, swapIndex+1);
        Collections.sort(copyList);

        int replaceIndex = 0;
        for (; replaceIndex < copyList.size(); replaceIndex++){
            if (value.equals(copyList.get(replaceIndex))){
                break;
            }
        }

        //If digits are duplicate in the list then we should need next greater digit
        for (; replaceIndex + 1 < copyList.size(); replaceIndex++){
            if (!copyList.get(replaceIndex).equals( copyList.get(replaceIndex+1))){
                Integer temp = copyList.get(replaceIndex+1);
                copyList.remove(replaceIndex+1);
                copyList.add(0, temp);
                break;
            }
        }

        Collections.reverse(copyList);
        Collections.reverse(integerList);

        StringBuilder str = new StringBuilder();
        integerList.forEach(str::append);

        System.out.println("Number : " + number);
        System.out.println("Next   : " + str.toString());

    }

    public static List ConvertToArray(int num){
        List integerList = new ArrayList<>();
        while (num > 0){
            int reminder = num %10;
            num = num/10;
            integerList.add(reminder);
        }
        return integerList;
    }
}

Comments are welcome.

No comments:

Post a Comment