Write a 'C' program .Input a and b .Find the smallest number greater than b by inter changing the digits of a and if not possible return -1
Answers
// C++ implementation to form the smallest
// number using at most one swap operation
#include <bits/stdc++.h>
using namespace std;
// function to form the smallest number
// using at most one swap operation
string smallestNumber(string num)
{
int n = num.size();
int rightMin[n], right;
// for the rightmost digit, there
// will be no smaller right digit
rightMin[n - 1] = -1;
// index of the smallest right digit
// till the current index from the
// right direction
right = n - 1;
// traverse the array from second
// right element up to the left
// element
for (int i = n - 2; i >= 1; i--)
{
// if 'num[i]' is greater than
// the smallest digit encountered
// so far
if (num[i] > num[right])
rightMin[i] = right;
else
{
// there is no smaller right
// digit for 'num[i]'
rightMin[i] = -1;
// update 'right' index
right = i;
}
}
// special condition for the 1st digit so that
// it is not swapped with digit '0'
int small = -1;
for (int i=1; i<n; i++)
if (num[i] != '0')
{
if (small == -1)
{
if (num[i] < num[0])
small = i;
}
else if (num[i] < num[small])
small = i;
}
if (small != -1)
swap(num[0], num[small]);
else
{
// traverse the 'rightMin[]' array from
// 2nd digit up to the last digit
for (int i = 1; i < n; i++)
{
// if for the current digit, smaller
// right digit exists, then swap it
// with its smaller right digit and
// break
if (rightMin[i] != -1)
{
// performing the required
// swap operation
swap(num[i], num[rightMin[i]]);
break;
}
}
}
// required smallest number
return num;
}
// Driver program to test above
int main()
{
string num = "9625635";
cout << "Smallest number: "
<< smallestNumber(num);
return 0;
}