Monday, 26 January 2015

Find next greatest number from digits of a given number

Find the smallest number that has same set of digits as n and is greater than n. 
If n is the greatest possible number with its set of digits, then print "not possible".

Examples:

Input:  n = "1234"
Output: "1243"

Input:  n = "1243"
Output: "1324"

Input:  n = "1324"
Output: "1342"

Input:  n = "1342"
Output: "1423"

Input: n = "4321"

Output: "Not Possible"

Input:  n = "5349762"
Output: "5362479"

Input: n = "53497766"
Output: "53646779"


Algorithm:

From the first few examples, we can see that the algorithm is to traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. Then replace this small number with the next highest traversed number. Then pick remaining traversed number plus the small number, sort them from smallest to largest and append them to the end. 
For a more complex level, handle duplicate numbers in the set. For handling duplicate numbers that needs to be sorted, we requires a set that accept duplicate numbers. Refer to blog on How to add duplicate entries to a Set for creating a set that accepts duplicate entries.


package com.prasune.coding;

import java.util.Set;
import java.util.TreeSet;

public class NextGreatestNumber {

      public static void main(String[] args) {
            printNextGreaterNumber(4321);
      }

      private static void printNextGreaterNumber(Integer number) {
            String nextGreaterNumber = null;
            String numberAsString = number.toString();
            Integer prevValue = 0;
            Set<Integer> numbersToSort =
                  new TreeSet<Integer>(new CustomComparator());        
           
            for (int i = numberAsString.length() - 1; 0 <= i; i--) {
                  Integer digit =                   Integer.parseInt(""+numberAsString.charAt(i));             
                  if(digit < prevValue){
                        Integer replacement = 
                                   getReplacementNumber(digit, numbersToSort);

                        nextGreaterNumber = numberAsString.substring(0, i)
                                          + replacement;
                        numbersToSort.add(digit);
                        nextGreaterNumber = appendSortedNumbers(
                                              nextGreaterNumber,                                                              numbersToSort,                                                                  replacement);
                        break;
                  } else{
                        prevValue = digit;
                  }    
                  numbersToSort.add(digit);
            }
            if(nextGreaterNumber != null){
                  System.out.println("Next greater number: " 
                                     + nextGreaterNumber);
            }else{
                  System.out.println("Not Possible");
            }          
      }

      private static Integer getReplacementNumber(Integer digit,                                                                  Set<Integer> numbersToSort) {
            Integer replacementNumber = 0;
            for (Integer number : numbersToSort) {
                  if(number > digit){
                        replacementNumber = number;
                        break;
                  }
            }
            return replacementNumber;
      }

      private static String appendSortedNumbers(String nextGreaterNumber,
                                                Set<Integer> numbersToSort,
                                                Integer replacement) {
            boolean isReplacementExcluded = false;
            StringBuilder greaterNumberString =
                                      new StringBuilder(nextGreaterNumber);
            for (Integer number : numbersToSort) {
                  if(!isReplacementExcluded && number == replacement){
                        isReplacementExcluded = true;                  
                  }else {
                        greaterNumberString.append(number);
                  }
            }
            return greaterNumberString.toString();
      }    
}




Sunday, 11 January 2015

How to add duplicate entries to a Set

There could be use cases in programming where you would require to store duplicate values in addition to sorting them. A Set implementation would do sorting for you but then the duplicate entries get eliminated.

A hack for countering this is to return false when the values are equal. A sample implementation of Set to allow duplicate entries are as follows:

Create a custom comparator as follows that does not return 0 when the entries are equal.

package com.prasune.coding;

import java.util.Comparator;

public class CustomComparator implements Comparator<Integer>
{
    @Override
    public int compare(Integer i1, Integer i2)
    {
        if(i1.compareTo(i2) == 0){
            return 1;
        }
        else{
            return i1.compareTo(i2);
        }
    }
}




Create a Set implementation using the above comparator and add numbers to the Set:

package com.prasune.coding;

import java.util.Set;
import java.util.TreeSet;

public class SetWithDuplicates {

      public static void main(String[] args) {
            Set<Integer> numbersToSort = new TreeSet<Integer>(new CustomComparator());
            numbersToSort.add(10);
            numbersToSort.add(12);
            numbersToSort.add(15);
            numbersToSort.add(11);
            numbersToSort.add(12);
            for (Integer number : numbersToSort) {
                  System.out.print(number);
                  System.out.print(" ");
            }
      }
}

You will get the output as:
10 11 12 12 15