Last Updated: 15 Mar, 2021
Maximum Swap
Easy
Asked in companies
Given a positive integer N, you can do the following operation at most once
a) Swap two digits of the integer N.
You need to determine the largest integer you can get by performing the above operation at most once.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.
The first line of each test case contains one integer ‘N’ denoting the number.
Output Format:
For each test case, print output one integer ‘X’, where ‘X’ is the largest integer you can get.
Print the output of each test case in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^9
Time limit: 1 sec
Approaches
The intuition here is that if there is a larger digit that is present later then swap these digits. It is optimal to swap the first such digit with the larger digit present after this digit position. The idea is to try to swap each digit with every other digit and then take the maximum number out of all numbers formed after swapping digits.
The algorithm is as follows :
- Convert the integer ‘N’ to string ‘S’.
- Iterate from ‘i’ = 0 to ‘|S| - 1’
- Declare an integer variable ‘ANS’ and set it to ‘NUM’.
- Iterate from ‘j’ = ‘i’ + 1 to ‘|S| - 1’,
- If ‘S[i]’ >= ‘S[j]’, then continue.
- Else swap(S[i], S[j]), since ‘S[j]’ > ‘S[i]’, this swap can give maximum ans.
- Update ‘ANS’ to max('ANS', Integer(S)).
- swap(S[i], S[j]), try all other options to get the maximum ans, so we need to swap it back to get back to the original state.
- If ‘ANS’ > 'N', return ‘ANS’.
- Return ‘N’.
The intuition here is that if there is a larger digit that is present later then swap these digits. It is optimal to swap the first such digit with the larger digit present after this digit position. We can do some pre-computation, to get the largest digit present after any other digit. For every digit ‘D’ in ‘N’, ‘LASTOCCURRENCEOFDIGIT[D]’ = position where it is present at last.
The algorithm is as follows :
- Convert the integer ‘N’ to string ‘S’.
- Declare an array ‘LASTOCCURRENCEOFDIGIT[]’ to store the last occurrence of the i-th digit.
- Iterate from ‘i’ = 0 to ‘|S| - 1'
- Set, ‘LASTOCCURRENCEOFDIGIT[S[i] - ‘0’]’ = ‘i’.
- Iterate from ‘i’ = 0 to ‘|S| - 1’
- Iterate backwards from ‘DIGIT’ = 9 to ‘S[i]’ - ‘0’ - 1,
- If ‘LASTOCCURRENCEOFDIGIT[DIGIT]’ > ‘i’,
- Swap('S[i]', ‘S[LASTOCCURRENCEOFDIGIT[DIGIT]]’), since this swap gives the maximum ‘S’.
- Return ‘Integer(S)’.
- If ‘LASTOCCURRENCEOFDIGIT[DIGIT]’ > ‘i’,
- Iterate backwards from ‘DIGIT’ = 9 to ‘S[i]’ - ‘0’ - 1,
- Return ‘N’.