Next Greater Number
Write a number ‘N’ (containing at most 10,000 digits), find the next grater number having the same digits. It is guaranteed that there exists a next greater number having the same digits as N.
Input specification:
Input1: The length of the string ‘N’.
Input2: The number ‘N’ in the form of a string.
Output Specification:
Return the next greater number having the same digits as ‘N’ in the form of a string.
Example 1:
Input 1: 3
Input 2: 182
Output: 218
Explanation:
The next greater number after 182 is 218 using {1,8,2}
Example 2:
Input 1: 4
Input 2: 2345
Output: 2354
Explanation:
The next greater number after 2345 is 2345 using {2,3,4,5}
Solution in Python 3:
#https://codewindow.in
#join our telegram channel
from itertools import permutations
r=int(input()) #length
n=input() #taking the input as a string
a = permutations(n, r)
#print(a)
y = [''.join(i) for i in a] # joining the digits to a y
y=sorted(y)
q=y.index(n) #finding the index of the input value from the list
#print(q)
print(y[q+1])
# Telegram @codewindowSolution in C++ :
//https://codewindow.in
//join our telegram channel @codewindow
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void swap(char *a, char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}
void findNext(char number[], int n)
{
int i, j;
for (i = n-1; i > 0; i--)
if (number[i] > number[i-1])
break;
if (i==0)
{
cout << "Next number is not possible";
return;
}
int x = number[i-1], smallest = i;
for (j = i+1; j < n; j++)
if (number[j] > x && number[j] < number[smallest])
smallest = j;
swap(&number[smallest], &number[i-1]);
sort(number + i, number + n);
cout << number;
return;
}
int main()
{
int n;
cin >> n;
char digits[n];
cin >> digits;
findNext(digits, n);
return 0;
}Solution in JAVA :
//https://codewindow.in
//join our telegram channel @codewindow
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static void swap(char ar[], int i, int j)
{
char temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
static void findNext(char ar[], int n)
{
int i;
for (i = n - 1; i > 0; i--)
{
if (ar[i] > ar[i - 1]) {
break;
}
}
if (i == 0)
{
System.out.println("Not possible");
}
else
{
int x = ar[i - 1], min = i;
for (int j = i + 1; j < n; j++)
{
if (ar[j] > x && ar[j] < ar[min])
{
min = j;
}
}
swap(ar, i - 1, min);
Arrays.sort(ar, i, n);
for (i = 0; i < n; i++)
System.out.print(ar[i]);
}
}
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String str = br.readLine();
findNext(str.toCharArray(), n);
}
}
Output:
4
2345
2354