Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:
Input: 12
Output: 21
Example 2:
Input: 21
Output: -1
Solution : (Same as next permutation)
class Solution
{
public:
void reverse(vector<int> &v, int start)
{
int end = v.size() - 1;
while (start <= end)
{
if (v[start] > v[end])
{
swap(v[start], v[end]);
}
start++;
end--;
}
return;
}
int nextGreaterElement(int n)
{
vector<int> v;
while (n > 0)
{
int x = n % 10;
v.insert(v.begin(), x);
n = n / 10;
}
int idx = -1;
for (int i = v.size() - 1; i > 0; i--)
{
if (v[i - 1] < v[i])
{
idx = i - 1;
break;
}
}
if (idx != -1)
{
int idx2 = idx + 1;
for (int i = idx + 1; i < v.size(); i++)
{
if (v[i] > v[idx] && v[i] <= v[idx2])
{
idx2 = i;
}
}
swap(v[idx], v[idx2]);
reverse(v, idx + 1);
}
else
{
return -1;
}
int num = 0;
for (int i = 0; i < v.size(); i++)
{
num = num * 10 + v[i];
if(num > INT_MAX/10){
return -1;
}
}
return num;
}
};