CareerCup

Correct me if I am mistaken here:

Take the last digit - keep comparing this with digits from the back (one by one) till you reach a digit that is lesser than the last digit. Now swap these two.

Now just sort the numbers in the portion that was compared (after the digit where the swap compared).

You have the next biggest number. This is O(N)+)(NLogN) = O(NLogN).

1462 won't work

My algorithm works for all the above mentioned cases.
Store the number in a character array (num) and traverse back from the last. As soon as it is found that the digit at the current index (i) is less compared to the element to its right,we have to find the smallest number in the right part starting from i+1 which just exceeds num[i]. Swap that number with num[i] and sort the right array in ascending order.

e.g. For 1342
i = 1 since it is less than its next element to the right (which is 4)
We find the nearest digit in the right array starting from index 2
and in this case the number is 4.
Swap them

So now the number is 1432

Then we sort the right part to get
1423

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
int searchJustBig(const char* num, char c, int lpos, int rpos);
int comp(const void* a, const void* b)
{
	char p = *(char*)a;
	char q = *(char*)b;
	if(p<q)
		return -1;
	else if(p>q)
		return 1;
	else
		return 0;
}
int main()
{
	cout<<"Enter the number ";
	char num[1024];
	scanf("%s", num);
	unsigned len = strlen(num);
	int i = len-2;
	char tmp = num[len-1];
	for(; i>=0; i--)
	{
		if(num[i] < tmp)
		{
			int val = searchJustBig(num, num[i], i+1, strlen(num)-1);
			swap(num[val], num[i]);
			qsort(num+i+1, strlen(num)-i-1, sizeof(char), comp);
			break;
		}
		else
		{
			tmp = num[i];
		}
	}
	if(i == -1)
		printf("NONE\n");
	else
		printf("%s\n", num);
}
int searchJustBig(const char* num, char c, int lpos, int rpos)
{
	if(lpos<rpos)
	{
		int mid = (lpos + rpos)/2;
		if(num[mid] <= c)
			return searchJustBig(num, c, lpos, mid);
		else
			return searchJustBig(num, c, mid+1, rpos);
	}
	else
	{
		if(num[lpos] > c)
			return lpos;
		return lpos-1;
	}
}

@ k kishore ultimate solution :)

int nextNumberWithSameDigits(int aNum)
{
if(aNum < 0)
throw new exception("Negative not implemented.");

if(aNum < 9)
return aNum;

CQueue<int> _q;
CStack<int> _s;

int aMod = 0;
int aTemp = aNum;
while(aTemp > 0)
{
aMod = aTemp % 10;
aTemp = aTemp / 10;

if(_q.empty() || aMod > _q.front())
{
_q.push(aMod);
}
else
{
_s.push(aMod);
break;
}
}

if(_s.empty())
return aNum;

while(!_q.empty())
{
if(_q.back() < aMod)
_s.push(_q.pop());
else
break;
}

aTemp = (aTemp * 10) + _q.pop();

while(!_q.empty() || !_s.empty())
{
int a;
if(!_q.empty() && !_s.empty())
a = _q.front() < _s.top()?_q.pop():_s.pop();
else if (_q.empty())
a = _s.pop();
else if(_s.empty())
a = _q.pop();

aTemp = (aTemp * 10) + a;
}

return aTemp;

}

Nice soln man

Working Python solution

def nextFromDigits(X):
    L = list(str(X))
    prev = '0'
    for i in reversed(range(len(L))):
        if L[i] < prev:        
            G = (j for j in xrange(i+1,len(L)) if L[j]>L[i])  # generator with suffix indices to elements larger than L[i]          
            k = min(G, key = L.__getitem__ )  
            L[i], L[k] = L[k], L[i]   #swap
            L[i+1:] = sorted(L[i+1:])
            return int(''.join(L))
        prev = L[i]            
    return -1  #does not exist
 
print nextFromDigits(1234)
print nextFromDigits(1243)
print nextFromDigits(4321)

Check also at: ideone.com/un873

Algo
Start from last element and keep a track of big element
If a small element is found update big and small and sort rest
else if big is found update big and continue search


char[] str1=str.toCharArray();
char temp=str1[l-1];
boolean dobreak=true;
System.out.println(temp);
int i=l-1;
for(int j=l-2;j>=0&& dobreak==true;j--)
{
if(temp<str1[j]){
temp=str1[j];
}
if(str1[j]<temp)
{
char temp2=str1[j];
str1[j]=str1[i];
str1[i]=temp2;
dobreak=false;
for(int x=j+1;x<=l-2;x++)
{
for(int y=x+1;y<=l-1;y++)
{
if(str1[x]>str1[y])
{
char temp3=str1[x];
str1[x]=str1[y];
str1[y]=temp3;
}
}
}
}


}


System.out.println(str1);

public boolean next_perm(int n[])
{
int l=n.length;
int i=0,j=0;
for(i=l-2;i>=0&&n[i]>=n[i+1];)i--;
if(i==-1)return false;
int x=n[i];
for(j=l-1;j>i&&n[j]<=x;)j--;
n[i]=n[j];
n[j]=x;
Arrays.sort(n,i+1,l);
return true;
}