Next Greater Element III

Easy
0/40
Average time to solve is 20m
profile
Contributed by
38 upvotes
Asked in companies
SalesforceMicrosoftApple

Problem statement

Alice and Bob were given homework to bring a number. As usual, Bob forgot to do it and asked Alice if he could copy her’s. Alice agreed to help him only if he rearranged the digits of her number such that the new number was strictly greater than the old one. Also, the teacher does not like big numbers, so Bob needs to make sure his number is as small as possible.

Help Bob rearrange the digits of Alice’s number to make a number greater than that of Alice and is smallest possible or print -1 when no such number exists.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains an integers ‘N’,  denoting Alice’s number.
Output Format: 
For each test case, print a single integer denoting the final number after rearranging the digits or -1 when no such number exists.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
2 <= N <= 2 * (10^9)

Time Limit: 1 sec
Sample Input 1:
2
225
66
Sample Output 1:
252
-1
Explanation for Sample Input 1:
In the first test case, 252 is the smallest possible number that can be made by rearranging the digits of 225 and is greater than 225. Another possible arrangement is 522, but it’s not the smallest possible.  

In the second test case,  66 can not be rearranged to make any other number.
Sample Input 2:
2
342 
39
Sample Output 2:
423 
93
Hint

Can you rearrange the digits of Alice’s number to find the final answer?

Approaches (2)
Brute Force

Bob needs to find a permutation of the digits of Alice’s number such that it is greater than Alice’s number but is smallest among all the other permutations greater than that of Alice’s number. 

So we can convert the number into a string and find all possible permutations of the string. Among all the permutations, we need to find the minimum string greater than that of Alice’s number.


 

Algorithm: 

  • Convert the number ‘N’ to a string ‘S’.
  • Initialize a string ‘ans’ to “-1”.
  • Generate all possible permutations of string ‘S’
    • If the current permutation is greater than ‘S’
      • If ‘ans’ is “-1”, then assign ‘ans’ to the current permutation.
      • Else update ‘ans’ to a minimum of ‘ans’ and current permutation.
  • Convert the string ‘ans’ to an integer ‘res’
  • Return the ‘res’
Time Complexity

O(L! * (L ^ 2 )), where ‘L’ is the count of digits in Alice’s number.


 

Generating all the permutations of the string has a time complexity of O(L! * L). For each permutation, we need to compare two strings, so total complexity becomes 

O(L! * (L^2)).


 

Space Complexity

O(L! * L), where ‘L’ is the count of digits in Alice’s number.


 

We are storing all the permutations of size ‘L’ so total space complexity becomes O(L! * L).


 

Code Solution
(100% EXP penalty)
Next Greater Element III
Full screen
Console