Keep a pointer ont the rightmost digit. Keep moving right until you find the number in increasing number. As soon as this breaks. stop. Swap the digit at the current position with the smallest digit, but larger than the current position digit, sort the array to the right of the current position in descending order.
explanation: NUMBER:759854 INDEX: 012356 Keep the pointer at index 6. Keep moving right as long as numbers are in increasing fashion. Stop at index 1. swap this digit with the smallest digit larger than 5 i.e. 8 78(9554) now sort the array in parenthesis in descending order ans : 784559 For the implementation you can actually create an array of length 10, to keep track of all the digits encounters while moving left. This will help in sorting as well (similar to counting sort). One pass will do the work. You can print the answer directly afterwards. With Regards Unknown On Thu, Sep 22, 2011 at 4:13 PM, Dheeraj Sharma <[email protected] > wrote: > in nlog(n) > > #include<iostream> > #include<conio.h> > #include<string.h> > #define swap(a,b,c) (c)=(a),(a)=(b),(b)=(c) > using namespace std; > int t; > void quicksort(char arr[],int left,int right) > { > if(left<right) > { > int piv=right; > int i=left,j=left; > while((i<right) && (j<right)) > { > if(arr[j]<arr[piv]) > { > swap(arr[i],arr[j],t); > i++; > } > j++; > } > swap(arr[i],arr[piv],t); > quicksort(arr,left,i-1); > quicksort(arr,i+1,right); > > } > } > int main() > { > char str[100],t; > int arr[100],i=0; > cin>>str; > int min=0; > int len=strlen(str); > while(str[i]) > { > if(str[i]<=str[min]) > min=i; > arr[i]=min; > i++; > } > i=len-1; > while((arr[i]==i)&&(i>0)) > i--; > swap(str[i],str[arr[i]],t); > > if(i>0) > quicksort(str,arr[i]+1,len-1); > cout<<str; > getch(); > } > > > On Thu, Sep 22, 2011 at 3:33 PM, Dheeraj Sharma < > [email protected]> wrote: > >> #include<iostream> >> #include<conio.h> >> #include<string.h> >> #define swap(a,b,c) (c)=(a),(a)=(b),(b)=(c) >> using namespace std; >> int main() >> { >> char str[100],t; >> cin>>str; >> >> int len=strlen(str); >> int i,x,boo=1; >> for(i=len-1;i>0&&boo;i--) >> { >> for(x=i-1;x>=0&&boo;x--) >> { >> if(str[x]<str[i]) >> { >> swap(str[x],str[i],t); >> boo=0; >> } >> } >> } >> if(i>0) >> { >> >> //Sorting... >> for(int l=x+2;l<len-1;l++) >> { >> int min=l; >> for(int k=l+1;k<len;k++) >> { >> if(str[k]<str[min]) >> min=k; >> } >> swap(str[min],str[l],t); >> } >> } >> cout<<str; >> >> >> getch(); >> } >> >> >> correct me..if m wrong.. >> >> >> On Thu, Sep 22, 2011 at 2:01 PM, Ratan <[email protected]> wrote: >> >>> @dheeraj ... ya u r ryt.... thnxs for the correction >>> >>> On Thu, Sep 22, 2011 at 1:30 PM, Dheeraj Sharma >>> <[email protected]> wrote: >>> > @Ratan: >>> > i think the next largest here would be 784559 >>> > >>> > On Thu, Sep 22, 2011 at 12:39 PM, Ratan <[email protected]> >>> wrote: >>> >> >>> >> @kartik : to some extent ur code is giving the right answer... btw >>> >> somehow check tis >>> >> let for example the no be 759854 >>> >> then the next biggest no is 794558 >>> >> btw ur program is giving 795854 which is undoubtedly wrong............ >>> >> the code would give more appropriate result if u sort the numbers from >>> >> from i to n on meeting the condition of (a[i-1]<a[i]) >>> >> >>> >> On Thu, Sep 22, 2011 at 11:53 AM, Ramakant Sharma < >>> [email protected]> >>> >> wrote: >>> >> > starting from right find first digit less then right most digit,if >>> no >>> >> > any >>> >> > digit is less,then move to next right most and compair ,,,,when >>> found >>> >> > exchange those no, >>> >> > now sort the no.s up to that index of the given no which is >>> exchanged: >>> >> > Ex: >>> >> > 43987723893239876 >>> >> > first required sequence: 439877238932[3]987[6] swap these no >>> >> > 439877238932[6]{987[3]} >>> >> > now sort in decreasing order 439877238932[6]{3789} this is the >>> required >>> >> > no >>> >> > ....correct me if any thing wrong >>> >> > >>> >> > >>> >> > >>> >> > >>> >> > >>> >> > -- >>> >> > You received this message because you are subscribed to the Google >>> >> > Groups >>> >> > "Algorithm Geeks" group. >>> >> > To post to this group, send email to [email protected]. >>> >> > To unsubscribe from this group, send email to >>> >> > [email protected]. >>> >> > For more options, visit this group at >>> >> > http://groups.google.com/group/algogeeks?hl=en. >>> >> > >>> >> >>> >> >>> >> >>> >> -- >>> >> Ratan Kumar >>> >> B. Tech >>> >> MNNIT, >>> >> Allahabad >>> >> >>> >> -- >>> >> You received this message because you are subscribed to the Google >>> Groups >>> >> "Algorithm Geeks" group. >>> >> To post to this group, send email to [email protected]. >>> >> To unsubscribe from this group, send email to >>> >> [email protected]. >>> >> For more options, visit this group at >>> >> http://groups.google.com/group/algogeeks?hl=en. >>> >> >>> > >>> > >>> > >>> > -- >>> > Dheeraj Sharma >>> > Comp Engg. >>> > NIT Kurukshetra >>> > >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]. >>> > For more options, visit this group at >>> > http://groups.google.com/group/algogeeks?hl=en. >>> > >>> >>> >>> >>> -- >>> Ratan Kumar >>> B. Tech >>> MNNIT, >>> Allahabad >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> *Dheeraj Sharma* >> Comp Engg. >> NIT Kurukshetra >> >> >> > > > -- > *Dheeraj Sharma* > Comp Engg. > NIT Kurukshetra > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
