Maximum Time

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Google inc

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
#5:40
#4:#5
Sample Output 1 :
15:40
14:55
Explanation For Sample Input 1 :
For first test case :

The maximum possible hour can be 15, and the maximum possible minutes can be 40.

For second test case :

The maximum possible hour can be 14, and the maximum possible minutes can be 55.
Sample Input 2 :
2
##:30
14:2#
Sample Output 2 :
23:30
14:29
Hint

Try finding all possible time.

Approaches (2)
Brute Force

The basic idea is to find all the possible times and return the maximum time out of those using recursion.

 

Here is the algorithm :

 

  1. Create a variable (say, ‘RES’) that will store the maximum possible time and initialize it with ‘00:00’.
  2. Create a variable (say, ‘IDX’) used for traversing the string, ‘STR’, and initialize it with 0.
  3. Call the helper function HELPER(STR, RES, IDX), which will find the maximum time.
  4. Finally, return the ‘RES’.
     

HELPER(STR, RES, IDX):  (‘HELPER’ function)

 

  1. 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.
  2. 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.
  3. 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).

 

  1. Check if ‘STR[0]’ is greater than 2.
    • Return FALSE.
  2. Check if ‘STR[0]’ is equal to 2 and ‘STR[1]’ is greater than 3.
    • Return FALSE.
  3. Check if ‘STR[3]’ is greater than 5.
    • Return FALSE.
  4. Finally, return TRUE..

 

findMax(STR, RES): (Function to find the maximum of ‘STR’ and ‘RES’).
 

  1. Run a loop from 0 to 5 (say, iterator ‘i’) to check each digit of the string.
  2. Check if ‘STR[i]’ is greater than ‘RES[i]’.
    • Return ‘STR’.
  3. Check if ‘STR[i]’ is smaller than ‘RES[i]’.
    • Return ‘STR’.
  4. Finally, return ‘STR’.
Time Complexity

O(1)

 

We assign digits to all the possible places of ‘STR’. The total possible number of strings that represents the possible time that can be made is 1050 i.e 3*5*7*10.
00:00, 00:01, 00:02...... 23:56, 23:57, 23:58, 23:59, 24:00.
O(480) ~ O(1)

But in code to make the implementation little easy we have taken maximum number that possible at last position.

There are 10 choices we can use for every 4 positions. So, the total number of combinations can be 10^4. For each possible combination, we check whether the time in the string is possible or not, which takes O(1) time, and we also find the maximum time which takes O(5) time. Therefore, the overall time complexity will be O((10^4)*5), i.e., O(1).

Space Complexity

O(1)

 

We use string ‘RES’ to store the maximum possible time, whose length will be 5. The recursive stack can contain the size of the string ‘STR’, i.e., 5. Therefore, the overall space complexity will be O(1).

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