Single Digit Change

Easy
0/40
Average time to solve is 10m
profile
Contributed by
5 upvotes
Asked in company
Amazon

Problem statement

You are given a positive integer ‘NUM’ consisting only of digits ‘6’ and ‘9’. You can change at most one digit (i.e ‘6’ to ‘9’, or ‘9’ to ‘6’). Your task is to find and return the maximum number you can obtain.

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

The first line of each test case will contain a single integer ‘NUM’.
Output Format: 
For each test case, return the maximum number you can get by changing at most one digit as described above.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 50
6 <= ‘NUM’ <= 10^9
‘NUM’ has only digits 6 and 9.

Time limit: 1 sec
Sample Input 1:
2
9
966
Sample Output 1:
9
996
Explanation of sample input 1:
In the first test case, there is only one digit, and if we change it to 6 then the obtained number will be smaller, so we do not change it.

In the second test case,  Changing the first digit results in 666.
Changing the second digit results in 996.
Changing the third digit results in 969.
The maximum number is 996.
Sample Input 2:
2
99999
69999
Sample Output 2:
99999
99999
Hint

In a weighted number system, the weight of the digit increases from right to left.

Approaches (1)
Greedy

The idea is to find the leftmost digit which is 6, and change it to 9, if all digits are 9 then we do not change any digit. The easiest way to do it is to first convert ‘NUM’ in a string using the inbuilt methods like to_string() in C++, str(), we will use cahr array in java because String is immutable in java and convert int to char Array, then replace the first occurrence of ‘6’ to ‘9’ and then again convert it to an integer using stoi() in C++, int() in python, and Integer.parseInt in java and return it. 

 

The steps are as follows:

  1. Convert ‘NUM’ to string, and let this string be ‘NUMSTR’.
  2. Iterate over ‘NUMSTR’, if the current character is ‘6’, then replace it with ‘9’ and break the loop.
  3. Return ‘NUMSTR’ by converting it to an equivalent integer.
Time Complexity

O(D), where 'D' is the number of digits in ‘NUM’.

 

Converting ‘NUM’ to string and vice versa takes O(D) times, iterating over string ‘NUMSTR’ also takes O(D) times, Thus, the overall time complexity will be O(D) + O(D) + O(D) = O(D). 

Space Complexity

O(D), where 'D' is the number of digits in ‘NUM’.

 

Space used by ‘NUMSTR’ will be O(D).

Code Solution
(100% EXP penalty)
Single Digit Change
Full screen
Console