Monday, December 22, 2014

Lexographical next greater Number

Problem stmt- If input is 13786 then output should be 13867


import java.util.*;

public class Solution {


    static int solveMeFirst(int a) {
        int len=Integer.toString(a).length();
        int ar[]=new int[len+1];
        int i=1,m=1;
        //double d;
        ar[i]=a%10; // ar[1]=6
        a=a/10; // 1378
        while(a>0)
            {
            if(ar[i]>a%10) // Iteration 1- 6>8 false; Iteration 2- 8>7 True
           {
          //  i++;    // 2
            ar[0]=a%10; // ar[0]=7; as soon as you get the number which is greater than it's previous one store the lesser one in the very first location of array
                if(a/10!=0) // in case if this is the first digit of the number we don't need the quotient for that
                a=a/10; //13
                break;
            }
            i++;
            ar[i]=a%10; //ar[2]=8
           a=a/10; // 137
       
        }
 
        if(a/10!=0) //Checking if only first digit is remaining the number
        for(int j=0;j<=i;j++)
           a=a*10;
            else
            a=0;
     
        if(i==len) // If all the digits are checked and we couldn't find two consecutive digits satisfying the condition, return 0
            return 0;
     else
         { // first swap the first digit to the very first greater digit
         for (int j=1;j<=i;j++)
             if(ar[0]<ar[j])
             {
             int temp=ar[0];
             ar[0]=ar[j];
             ar[j]=temp;
             break;
         }
   //Calculate the next Lexographical greater Number
      for (int j=0;j<=i;j++)
          {
          for (int k=1;k<=i-j;k++)
              m=m*10;
          //m=d.intValue();
          a=a+(ar[j]*m);
          m=1;
      }
         return a;
     }
   
   }


 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int _a;
        _a = in.nextInt();
       // int _b;
        //_b = in.nextInt();
        int sum;
        sum = solveMeFirst(_a);
     if(sum!=0)
        System.out.println(sum);
     else
         System.out.println("No Answer");
     
   }
}

No comments:

Post a Comment