Q. Generate a number just immediate to the given number where generated number is the permutation of digits of the number.

  e.g
 INPUT               1234  
OUTPUT            1243    
   
  INPUT               65  
 OUTPUT            No  such  number  exists

 INPUT                345576
 OUTPUT             345657

 METHOD 1

A  very  naive  method  is  to  form  all  permutations  and  then  find  the  next  immediate  successor. It  is  highly  not  recommended  as  then  it  will  take  only  few  seconds  for  you  to  get  disqualified

METHOD 2

Yeah,  a  method  in  which  you  store  every  element  in  an  array  like

e.g   345576

a=  | 3 | 4 | 5 | 5 | 7 | 6 |

Now  you  take  the  last  element i.e 6  and  then  compare  it  with  7,5,5,4,3  to  find  the  first  minimum  which  is  5

and  then  swap  6  and  5  to  form

a=  | 3 | 4 | 5 | 6 | 7 | 5 |

Now  we  have  to  sort  the  array  from  positions  1  to  0  in  ascending  order

that  is  a=  | 3 | 4 | 5 | 6 | 5 | 7 |

For  sorting,,
we  are  opting  count  sort

We  have  to  keep  the  count[10]  of  size  10  where  index  is  the  key  and  count  is  its  value.  

Basic  funda  was  to  replace  a  digit  having  low  weight(unit place or tens...) but greater  than  any  digit  which  is  less  in  magnitude   but  is  having  higher weight  than  that.

Time  Complexity=O(n^2)

Space Complexity=O(n)

#include<stdio.h>

int main()

{

int n=48298;

int bresult=0;

int length=0;

int temp=n;

int hash[10]={0,0,0,0,0,0,0,0,0,0};

int mark;

int result=0;

int numarr[10];

for(int k=0;k<10;k++)

numarr[k]=11;

for(int k=0;k<10;k++)

{

if(temp==0)

break;

numarr[k]=temp%10;

temp=temp/10;

length++;

}

for(int k=0;k<=length-1;k++)

{

for(int i=k+1;i<=length;i++)

{

if(numarr[i]<numarr[k])

{

bresult=1;mark=i;

//swap k and mark

int stemp=numarr[k];

numarr[k]=numarr[mark];

numarr[mark]=stemp;

for(int k1=0;k1<mark;k1++)

hash[numarr[k1]]++;

break;

}

}

if(bresult==1)

break;

}

if(bresult==1)

{

int k2=0;

for(int k1=9;k1>=0;k1--)

{

if(hash[k1]>0)

{

while(hash[k1]>0)

{

numarr[k2++]=k1;

hash[k1]--;

}

}

}

for(int k1=9;k1>=0;k1--)

{

if(numarr[k1]==11)

continue;

else

{

result=10*result+numarr[k1];

}

}

printf("%d",result);

}

if(bresult==0)

printf("No value is found");

return 0;

}

Hope  you  all  find  it  useful. Please  inform  me  when  you  find  anything  challenging  to  understand  or  you  want  to  provide  me  suggestions  for  improvement.

Thanks  for  all  your  support