Wednesday, May 11, 2016

Next greater number with same set of digits

This is pretty interesting question I came across when facing an interview.

The question was pretty straight forward, you have given a number and you have to find the next greater number with the same set of digits as in the given number. So for an instance if Number is:
  1. 1234 then output should be 1243
  2. 4321 then output should be not possible since its the largest among all the possible numbers with the same digits as in 1234
  3. For other cases we have to develop the algorithm (:D).
Now coming to the solution of this problem, one straight forward algorithm would be:
  1. Find all the possible combination of the string (given number) and collect it in a Sortable Collection like TreeSet and take the next element after the given number. This is pretty straight forward approach but it is waste since we have to calculate the full set of numbers that are possible to get generated and then find the next number in the TreeSet. This is simple to understand but memory wise, order wise and space wise pretty heavy.
    Although I have given this answer only :D, but the interviewer was happy with it at all. Since there are better approaches to this.
  2. Next approach is pretty simple but a bit difficult to understand. Here it goes:
    1. First 2 condition will be same as the ascending and descending one.
    2. If the case is different then we will :
      1. take pair of digits from right where right digit is greater then left digit, and mark the index to be right digit index - 1.
      2. Then we have to take the smallest digit from the right hand side digits of the marked index which is greater then the indexed digit
      3. Then sort the right side of the index digit in ascending order.
      4. What, what what :D
    3. Lets take an example: 54362
      1. In this example start from the right in pair, (2,6) [we will ignore since 2<6] and move to next pair that is (6,3). This is correct pair since 6>3.
      2. So our marking index would be 2 and the number to be updated is 3.
      3. Now taking the number which appears in right side of index number(ie 2) and is smallest among them but larger then 3.
      4. In this case it is 6 only since 2 is smallest but 2>3 is false.
      5. So we swap 3 and 6 which will make the number as 54632 and sort the right hand of index(2) that means numbers 3,2 have to be sorted which is true in this case.
Lets make the program of this. Here it goes:

MyData.java
import java.util.Arrays;

/**
 * @author ankur
 *
 */
public class MyData {

 private int n;
 private int nAsc;
 private int nDesc;
 private int[] nIntArr;
 private int length;
 
 private String sAsc;
 private String sDesc;
 
 
 public MyData(int n){
  this.n = n;
  
  process();
 }
 
 private void process(){
  String s = "" + this.n;
  char [] sArr = s.toCharArray();
  
  nIntArr = new int[sArr.length];
  for(int i=0, len=sArr.length; i<len; i++){
   nIntArr[i] = Integer.parseInt("" + sArr[i]);
  }
  Arrays.sort(sArr);
  sAsc =  new String(sArr);
  sDesc = new StringBuffer(sAsc).reverse().toString();
  nAsc = Integer.parseInt(sAsc);
  nDesc = Integer.parseInt(sDesc);
  length = this.sAsc.length();
 }
 
 public int getN() {
  return n;
 }
 public void setN(int n) {
  this.n = n;
 }

 public int getnAsc() {
  return nAsc;
 }

 public void setnAsc(int nAsc) {
  this.nAsc = nAsc;
 }

 public int getnDesc() {
  return nDesc;
 }

 public void setnDesc(int nDesc) {
  this.nDesc = nDesc;
 }

 public String getsAsc() {
  return sAsc;
 }

 public void setsAsc(String sAsc) {
  this.sAsc = sAsc;
 }

 public String getsDesc() {
  return sDesc;
 }

 public void setsDesc(String sDesc) {
  this.sDesc = sDesc;
 }

 public int[] getnIntArr() {
  return nIntArr;
 }

 public void setnIntArr(int[] nIntArr) {
  this.nIntArr = nIntArr;
 }

 public int getLength() {
  return length;
 }

 public void setLength(int length) {
  this.length = length;
 }
 
 
}

Main.java
package com.av.ngnsd;

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

public class Main {

 public static void main(String[] args) {
  MyData myData = new MyData(54362);
  try{
   int nextNum = process(myData);
   System.out.println("Next number is " + nextNum);
  }catch(Exception ex){
   //ex.printStackTrace();
   System.out.println(ex.getMessage());
  }
 }
 public static int process(final MyData n) throws Exception{
  int result = 0;
  int nDesc = n.getnDesc();
  int nAsc = n.getnAsc();
  if(nDesc == n.getN()){
   throw new Exception("Not possible");
  }else if(nAsc == n.getN()){
   String s = "" + nAsc;
   result = Integer.parseInt(s.substring(0, s.length()-2) + "" + s.charAt(s.length()-1) + s.charAt(s.length()-2));  
  }else{
   //TODO the main code
   int []nCharArr = n.getnIntArr();
   int indexOfChange = -1;
   for(int i=n.getLength()-1; i>0; i--){
    if(nCharArr[i]>nCharArr[i-1]){
     indexOfChange = i;
     break;
    }
   }
   
   if(indexOfChange <= 0){
    throw new Exception("Not possible");
   }
   else{
    int numberToBeSwapped = nCharArr[indexOfChange-1], smallestIndex = indexOfChange;
    //getting the smallest among the right side of the index which is greater then index digit
    for(int i=indexOfChange+1; i<n.getLength(); i++){
     if(numberToBeSwapped < nCharArr[i] && nCharArr[i] < nCharArr[smallestIndex] ){
      smallestIndex = i;
     }
    }
    
    //swapping the 2 digits
    int temp = numberToBeSwapped;
    nCharArr[indexOfChange-1] = nCharArr[smallestIndex];
    nCharArr[smallestIndex] = temp;
    
    //for sorting the right hand side of the index
    List<Integer> nArrayList = new ArrayList<Integer>();
    for(int i=indexOfChange+1; i<n.getLength(); i++){
     nArrayList.add(nCharArr[i]);
    }
    
    //int indexOfChangeCopy = indexOfChange;
    Collections.sort(nArrayList);
    for(int num:nArrayList){
     nCharArr[++indexOfChange] = num;
    }
    StringBuilder strNum = new StringBuilder();
    for (int num : nCharArr) 
    {
         strNum.append(num);
    }
    result = Integer.parseInt(strNum.toString());
   }
  }
  
  return result;
 }
 
}


No comments:

Post a Comment