Last Updated: 16 Mar, 2021
Maximum Possible Time
Easy
Asked in companies
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.
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
Approaches
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).
Similar problems