Maximum Possible Time

Easy
0/40
Average time to solve is 10m
7 upvotes
Asked in companies
MicrosoftAmazonGrofers

Problem statement

Given an array/list ‘ARR’ having 4 integer digits only. The task is to return the maximum 24 hour time that can be formed using the digits from the array.

Note:

The minimum time in 24-hour format is 00:00, and the maximum is 23:59. If a valid time cannot be formed then return -1.

Example:

We have an array ARR = {1, 2, 3, 4} so the maximum time that will be formed will be 23:41.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains four integers.
Output format: 
For each test case, return the maximum time if found otherwise return -1.

Output for each test case is printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just return the valid string.
Constraints: 
1 <= T <= 10
0 <= ARR[i] <= 9

Time Limit: 1 sec
Sample Input 1:
2
1 2 3 4
5 5 5 5
Sample Output 1:
23:41
-1
Explanation 1:
For the first test case, 
The valid 24-hour times are "12:34", "12:43", "13:24", "13:42", 
"14:23", "14:32", "21:34", "21:43", "23:14", and "23:41". Out of all 
these, "23:41" is the maximum.

For the second test case, 
There are no valid 24-hour times as "55:55" is not valid.
Sample Input 2:
2
0 0 0 0
0 1 0 0
Sample Output 2:
00:00
10:00
Hint

Try to think by generating all possible permutations and find the maximum possible time.

Approaches (1)
Maximum Possible Time

Approach:

  • The basic idea is that we will iterate over all the permutations of the 4 digits and check whether we are able to form a valid 24 Hr format time. If so we will then also find the maximum possible time.
  • Here we will use the ‘NEXT_PERMUTATION’ method to find all the permutations.

 

Algorithm:

  • There are two conditions for valid 24 Hr format time:
    • The first two digits i.e the hour should be less than 24.
    • The last two digits i.e the minutes should be less than 60.
  • First, create a ‘MAX_TIME’ variable initially equal to -1 to store the maximum time.
  • Firstly sort the array ‘ARR’ for the generation of all the permutations otherwise we will not get all possible permutations.
  • Now run a loop over all the permutations of the 4 digits.
  • In each iteration, we check whether we could form a valid time based on the above two conditions.
  • If so, then we will also update the ‘MAX_TIME’ variable in order to track the maximum valid time seen till now.
  • If ‘MAX_TIME’ is equal to -1 then return “-1” in the form of string.
  • Otherwise, return string as (MAX_TIME/60:MAX_TIME%60).
Time Complexity

O(1).

 

The total number of permutations will be 4! = 24. Since the length of the array is fixed, therefore to generate all the permutations will be done in constant time.  Also, each iteration takes a constant time to process and since the total number of permutations is fixed therefore it will take 24*O(1) time. Thus total time complexity will be O(1) + O(1)  = O(1) time. 

Space Complexity

O(1).

 

In the algorithm, we keep the permutations for the input digits, which are in total 24, i.e. a constant number regardless of the input.

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