Maximum Possible Time
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

Question

Maximum Possible Time

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

Accepted Answer

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).

Space Complexity: O(1)Explanation:

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.

Time Complexity: O(1)Explanation:

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.

Java (SE 1.8)

/*
    Time complexity: O(1)
    Space Complexity: O(1)
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution {

	private static void swap(ArrayList A, int i, int j) {

		int tmp = A.get(i);
		A.set(i, A.get(j));
		A.set(j, tmp);

	}

	private static void reverse(ArrayList A, int i, int j) {

		while (i < j) {
			swap(A, i++, j--);
		}
	}

	private static boolean nextPermutation(ArrayList A) {
		if (A == null || A.size() <= 1) {
			return false;
		}

		int i = A.size() - 2;

		while (i >= 0 && A.get(i).intValue() >= A.get(i + 1).intValue()) {

			// Find 1st id i that breaks descending order.
			i--;
		}

		if (i >= 0) {
			// If not entirely descending.

			// Start from the end.
			int j = A.size() - 1;

			while (A.get(j).intValue() <= A.get(i).intValue()) {
				// Find rightmost first larger id j.
				j--;
			}

			// Switch i and j.
			swap(A, i, j);

			// Reverse the descending sequence.
			reverse(A, i + 1, A.size() - 1);

			return true;
		} else {
			// Reverse the sequence.
			reverse(A, 0, A.size() - 1);
			return false;
		}

	}

	public static String maxPossibleTime(ArrayList arr) {

		// Create a variable to store the valid maximum possible time.
		int maxTime = -1;

		// sort the array to generate all the permuations.
		Collections.sort(arr);

		// Iterate over all the permutaions one by one and for each valid time we will update the maximum time.
		do {
			int hour = arr.get(0) * 10 + arr.get(1);
			int minute = arr.get(2) * 10 + arr.get(3);

			if (hour < 24 && minute < 60) {
				int newTime = hour * 60 + minute;
				if (newTime > maxTime) {
					maxTime = newTime;
				}
			}
		} while (nextPermutation(arr));

		// To store the answer.
		StringBuilder ans = new StringBuilder();

		if (maxTime == -1) {
			ans.append("-1");
			return ans.toString();
		} else {

			if (maxTime / 60 < 10) {
				ans.append('0');
				ans.append((char) ((maxTime / 60) + '0'));
			} else {
				ans.append(String.valueOf(maxTime / 60));
			}

			ans.append(':');

			if (maxTime % 60 < 10) {
				ans.append('0');
				ans.append((char) ((maxTime % 60) + '0'));
			} else {
				ans.append(String.valueOf(maxTime % 60));
			}
			return ans.toString();
		}
	}
}

C++ (g++ 5.4)

/*

    Time complexity: O(1)

    Space Complexity: O(1)

*/



#include

#include

#include



string maxPossibleTime(vector &arr) {



	// Create a variable to store the valid maximum possible time.

	int maxTime = -1;



	// Sort the array to generate all the permuations.

	sort(arr.begin(), arr.end());



	// Iterate over all the permutaions one by one and for each valid time we will update the maximum time.

	do {

		int hour = arr[0] * 10 + arr[1];

		int minute = arr[2] * 10 + arr[3];



		if (hour < 24 && minute < 60) {

			int newTime = hour * 60 + minute;

			if (newTime > maxTime) {

				maxTime = newTime;

			}

		}

	} while (next_permutation(arr.begin(), arr.end()));





	if (maxTime == -1) {

		return "-1";

	} else {

		ostringstream strstream;

		strstream << setw(2) << setfill('0') << maxTime / 60 << ":" << setw(2) << setfill('0') << maxTime % 60;

		return strstream.str();

	}

}

Python (3.5)

'''
    Time complexity: O(1)
    Space Complexity: O(1)
'''

from itertools import permutations

def maxPossibleTime(arr):
    
    # Create a variable to store the valid maximum possible time.
    maxTime = -1
    
    # Sort the array to generate all the permutations.
    arr.sort()
    
    perm = list(permutations(arr))
    
    while len(perm) > 0:
        l = perm[0]
        hour = l[0] * 10 + l[1]
        minute = l[2] * 10 + l[3]
        
        if hour < 24 and minute < 60:
            newTime = hour * 60 + minute
            if newTime > maxTime:
                maxTime = newTime
                
        perm.pop(0)
        
    if maxTime == -1:
        return "-1"
        
    else:
        return str(maxTime // 60).zfill(2) + ":" + str(maxTime % 60).zfill(2)

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:

Example:

Input format:

Output format:

Note:

Constraints:

Top Blinkit Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern