Last Updated: 2 Sep, 2021
Maximum Time
Moderate
Asked in company
You are preparing for google interviews. You came across a problem where you have a string ‘STR’, representing the time in ‘hh:mm’ (24 hr format). Some of the digits are blank, which is represented by ‘#’. Replace the ‘#’ such that the time represented by this string is the maximum possible.
Example :
Given ‘STR’ : #5:40
Maximum time possible can be : 15:40
Input Format :
The first line of input contains an integer ‘T’, the number of test cases.
The first line of each test case contains the string ‘STR’, representing the time.
Output Format :
For each test case, print a string representing the maximum possible time.
Output for each test case will be printed 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 <= 50
The string ‘STR’ is always valid.
Time Limit : 1 sec
Approaches
The basic idea is to find all the possible times and return the maximum time out of those using recursion.
Here is the algorithm :
- Create a variable (say, ‘RES’) that will store the maximum possible time and initialize it with ‘00:00’.
- Create a variable (say, ‘IDX’) used for traversing the string, ‘STR’, and initialize it with 0.
- Call the helper function HELPER(STR, RES, IDX), which will find the maximum time.
- Finally, return the ‘RES’.
HELPER(STR, RES, IDX): (‘HELPER’ function)
- Check if the size of ‘STR’ is equal to ‘IDX’.
- Check if the ‘STR’ has the possible time or not by calling the isPossible(STR) function.
- Update ‘RES’ by a maximum of ‘STR’ and ‘RES’ by calling the findMax(STR, RES) function.
- Check if the ‘STR’ has the possible time or not by calling the isPossible(STR) function.
- Check if ‘STR[IDX]’ is not equal to ‘#’ or ‘STR[IDX]’ is equal to ‘:’.
- Recursively call the ‘HELPER’ function by passing ‘IDX’ + 1 in the function.
- Else, run a loop from 0 to 9 (say, iterator ‘i’) used to assign the digits to the string.
- Update ‘STR[IDX]’ by ‘i’.
- Recursively call the ‘HELPER’ function by passing ‘IDX’ + 1 in the function.
isPossible(STR): (Function to check whether the time is possible or not).
- Check if ‘STR[0]’ is greater than 2.
- Return FALSE.
- Check if ‘STR[0]’ is equal to 2 and ‘STR[1]’ is greater than 3.
- Return FALSE.
- Check if ‘STR[3]’ is greater than 5.
- Return FALSE.
- Finally, return TRUE..
findMax(STR, RES): (Function to find the maximum of ‘STR’ and ‘RES’).
- Run a loop from 0 to 5 (say, iterator ‘i’) to check each digit of the string.
- Check if ‘STR[i]’ is greater than ‘RES[i]’.
- Return ‘STR’.
- Check if ‘STR[i]’ is smaller than ‘RES[i]’.
- Return ‘STR’.
- Finally, return ‘STR’.
The basic idea is to assign digits to the string greedily to maximize the time. Assign all the digits individually to the string.
Here is the algorithm :
- Check if ‘STR[0]’ and ‘STR[1]’ is equal to ‘#’.
- Update ‘STR[0]’ to 2 and ‘STR[1]’ to 3.
- Check if ‘STR[0]’ is equal to ‘#’ and ‘STR[1]’ is not equal to ‘#’.
- If ‘STR[1]’ is smaller than 4, update ‘STR[0]’ to 2.
- Else, update ‘STR[0]’ to 1.
- Check if ‘STR[0]’ is not equal to ‘#’ and ‘STR[1]’ is equal to ‘#’.
- If ‘STR[0]’ is smaller than 2, update ‘STR[1]’ to 9.
- Else, update ‘STR[1]’ to 3.
- Check if ‘STR[3]’ is equal to ‘#’.
- Update ‘STR[3]’ to 5.
- Check if ‘STR[4]’ is equal to ‘#’.
- Update ‘STR[4]’ 9.
- Finally, return ‘STR’.