PROBLEM LINK:
Author: rocknot
Tester: ramagrawal2001
Editorialist: rocknot
DIFFICULTY:
MEDIUM
PREREQUISITES:
implementation sorting searching
PROBLEM:
Aditya completed his masters in Computer engineering. So he decided to contribute in a opensource project before applying for a job. While zooming through Git-hub projects he found an interesting project related to encryption of 32 bit systems. He was interested in this project so he decided to contribute in it. So he downloaded the source code of this project and while compiling error was detected. He went through documentation and source code of this project and realized that implementation of 32 bit integer system was wrong so he needs to fix it. According to documentations 32 bit integer system is implemented as follows.
-
It takes 32 bit integer N
-
as a input and returns an encrypted integer. Encryption is as follows:-
-
Encryption will rearrange the order of digits such that the new element formed is exactly greater than the original integer. You are given an integer N
you need to find a 32 bit integer which is exactly next greater element than it formed by rearranging the digits. If it is not possible to form such an integer less than 2^{31} -1 return “-1”.
EXPLANATION:
first we need transverse the integer from the last and find if all the elements are arranged in decreasing order if all the elements are in decreasing order then it is not possible to get element greater than it so return -1.
if any element is not in decreasing order set it as current element we need to transverse from next element till end and find out greatest element and swap it with current element and sort the remaining positions then check if number is greater than 2^{31} -1 if it is not greater than . if it is greater than 2^{31} -1 then print -1
SOLUTIONS:
Solution
#include <bits/stdc++.h>
using namespace std;
int nextGreaterElement(int n) {
vector<int> v;
while(n){
v.insert(v.begin(), n%10);
n /= 10;
}
int i = v.size()-2;
for(; i >= 0; i--){
if(v[i] < v[i+1])
break;
}
if(i < 0)
return -1;
int num = INT_MAX;
int pos = 0;
for(int j = i+1; j < v.size(); j++){
if(v[j] > v[i] && v[j] < num){
num = v[j];
pos = j;
}
}
swap(v[i], v[pos]);
sort(v.begin()+i+1, v.end());
num = 0;
for(auto nm : v){
long long res = num;
res *= 10;
if(res > INT_MAX) return -1;
num *= 10;
if(INT_MAX - num < nm) return -1;
num += nm;
}
return num;
}
int main(){
int T;
cin>>T;
while(T--){
int N;
cin>>N;
N=nextGreaterElement(N);
cout<<N<<endl;
}
return 0;
}