Wednesday, December 3, 2008

Find the next biggest number from the digits in the number.

If input is 8999 the next biggest number is 9899.
If input is 14562 the next biggest number is 14625.
using namespace std;
//SWAP 2 CHARACTERS
void swap(char* ch1, char* ch2)
{
char t;
t = *ch1;
*ch1 = *ch2;
*ch2 = t;
}
//USED IN QUICK SORT FOR SORTING AROUND THE PIVOT
int partition(char* ptr, int low, int high)
{
char key = ptr[low];
int i = low+1;
int j = high;
while(high > i && ptr[i] <= key)i++;
while(ptr[j] > key) j--;
if(i < j)
{
swap(ptr[i],ptr[j]);
}
else
{
swap(ptr[j],ptr[low]);
}
return j;

}
//RECURSSIVE QUICK SORT
void quicksort(char * ptr, int low, int high)
{
if( high > low)
{
int idx = partition(ptr,low,high);
quicksort(ptr,low,idx-1);
quicksort(ptr,idx+1,high);
}

}
//NEXT BIGGEST
void NextBiggest(char * val){

size_t len = strlen(val);
bool swapped = false;
// case : 9788 o/p:9887
//IF THERE IS ANY NUMBER IN OTHER PLACE, SMALLER THAN THE UNITth PLACE THE SWAP THEM
// AND YOU HAVE FOUND THE NEXT BIGGEST NUMBER
for(int i = len-2; i >= 1; i--)
{
if(val[len-1] > val[i]){
swap(val[len-1],val[i]);
swapped = true;
break;
}
}
//case : 145621 o/p:151246
//case 8997 o/p:9789
//IN CASES AS SHOWN ABOVE CHECK EVERY ALTERNATE DECIMAL PLACE VALUE, IF YOU FIND A SMALLER VALUE IN THE HIGHER DECIMAL PLACE SIMPLY SWAP THEM AND SORT THE INPUT FROM THAT POSITION.
if(swapped == false)
{
int i = 0;
for(i = len-2; i >=1; i--)
{
if(val[i] > val[i-1])
{
swap(val[i],val[i-1]);
swapped = true;
break;
}

}
if(swapped == true)
{
char* ptr = &val[i];
quicksort(ptr,0,(len - (ptr-val)-1));
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
char numeric [256];
memset(numeric,0,256);
cin >> numeric;
NextBiggest(numeric);
cout < < "The next biggest val is :" < < numeric;
return 0;
}

No comments: