Maximum Swap

Easy
0/40
Average time to solve is 15m
profile
Contributed by
42 upvotes
Asked in companies
AppleIBMAmazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4589
99538
Sample Output 1:
9584
99835
Explanation Of Sample Input 1:
For the first test case, swap the first digit with the last digit, So, return 9584.
For the second test case, swap the third digit with the last digit. So, return 99835.
Sample Input 2:
2
4321   
18
Sample Output 2:
4321
81
Explanation Of Sample Input 2:
For the first test case, the number given is biggest among all possible answers, So, return 4321.
For the second test case, swap the first digit with the last digit. So, return 81.
Hint

Can you think of changing one digit at a time and check all the possible combinations?

Approaches (2)
Brute Force Approach

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 :

  1. Convert the integer ‘N’ to string ‘S’.
  2. 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’.
  3. Return ‘N’.
Time Complexity

O(logN * logN), where N is the given number.

 

Here we are iterating over all the pairs of digits of N which is of the order logN * logN. So, the overall time complexity is O(logN * logN).

Space Complexity

O(1)

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Maximum Swap
Full screen
Console