Sponsored
Sponsored
Generate all possible permutations of the given 4 digits and check each permutation to see if it forms a valid time in the 24-hour format. Maintain the latest valid time found during this process.
Time Complexity: O(24), because there are 4! (24) permutations to check.
Space Complexity: O(1), additional space relative to input size is constant (ignores permutations' storage).
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <string>
5
6using namespace std;
7
8string largestTimeFromDigits(vector<int>& arr) {
9 string maxTime = "";
10 sort(arr.begin(), arr.end());
11 do {
12 int hours = arr[0] * 10 + arr[1];
13 int minutes = arr[2] * 10 + arr[3];
14 if (hours < 24 && minutes < 60) {
15 string curTime = to_string(hours).substr(0, 2) + ":" + (minutes < 10 ? "0" : "") + to_string(minutes);
16 if (maxTime.empty() || curTime > maxTime) {
17 maxTime = curTime;
18 }
19 }
20 } while (next_permutation(arr.begin(), arr.end()));
21 return maxTime;
22}
23
24// Example Usage:
25// int main() {
26// vector<int> arr = {1, 2, 3, 4};
27// cout << largestTimeFromDigits(arr) << endl; // Output: "23:41"
28// }
29This C++ solution first sorts the digits to facilitate permutations using std::next_permutation, which is efficient because it modifies the arrangement of elements directly. Within each permutation, it checks the validity of the hours and minutes and keeps track of the largest time found in lexicographical comparison. It returns the largest formatted time discovered or an empty string.
Sort the digits in descending order and attempt to form the largest possible hour and minute values by greedily assigning the largest permissible value to each time unit, reducing failures due to invalid hours or minutes promptly.
Time Complexity: O(1440) at maximum since it iterates through all minute combinations before valid time finding prematurely.
Space Complexity: O(1), as the only additional space use is from baselines and temporary variables.
1def largestTimeFromDigits(arr):
2 arr.
This Python solution iteratively attempts to create valid times by testing every potential hour and minute combination from the largest possible (23:59) down to (00:00). For each valid time, it reverse sorts and compares the formed digits with the sorted input array. If they match, it returns that time formatted as 'HH:MM'. The greedy reduction of the time possibilities prevents unnecessary permutations.