Given an array of 4 digits, return the largest 24 hour time that can be made.
The smallest 24 hour time is 00:00, and the largest is 23:59. Starting from 00:00, a time is larger if more time has elapsed since midnight.
Return the answer as a string of length 5. If no valid time can be made, return an empty string.
Example 1:
Input: [1,2,3,4]
Output: “23:41”Example 2:
Input: [5,5,5,5]
Output: “”Note:
A.length == 4
0 <= A[i] <= 9
Bruteforce Algorithm to Compute the Largest Time for Given Digits
Since there are only four digits, the easist algorithm would be to bruteforce with 3 loops – and calculate the fourth index by subtracting from 6 i.e. 0+1+2+3=6. Then we also need to check the validatity of each possible combination and find out the largest time which can be made.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution { public: string largestTimeFromDigits(vector<int>& A) { int ans = -1; string time = ""; for (int i = 0; i < 4; ++ i) { for (int j = 0; j < 4; ++ j) { if (i != j) { for (int k = 0; k < 4; ++ k) { if (k != i && k != j) { int l = 6 - i - j - k; int hours = 10 * A[i] + A[j]; int mins = 10 * A[k] + A[l]; if (hours < 24 && mins < 60) { int curTime = hours * 60 + mins; if (curTime > ans) { ans = curTime; time = std::to_string(A[i]) + std::to_string(A[j]) + ":" + std::to_string(A[k]) + std::to_string(A[l]); } } } } } } } return ans >= 0 ? time : ""; } }; |
class Solution {
public:
string largestTimeFromDigits(vector<int>& A) {
int ans = -1;
string time = "";
for (int i = 0; i < 4; ++ i) {
for (int j = 0; j < 4; ++ j) {
if (i != j) {
for (int k = 0; k < 4; ++ k) {
if (k != i && k != j) {
int l = 6 - i - j - k;
int hours = 10 * A[i] + A[j];
int mins = 10 * A[k] + A[l];
if (hours < 24 && mins < 60) {
int curTime = hours * 60 + mins;
if (curTime > ans) {
ans = curTime;
time = std::to_string(A[i]) +
std::to_string(A[j]) + ":" +
std::to_string(A[k]) +
std::to_string(A[l]);
}
}
}
}
}
}
}
return ans >= 0 ? time : "";
}
};The runtime complexity is O(1) constant as the constraints are already given and we only need to loop 64 times. The coding style isn’t great as too many code indent – but we may improve it slightly by inverting the if statement.
Clock 3:30
Enumerate Digits using next_permutation from C++ STL
There are a lot of nice routines from the STL::algorithms header. The next_permutation or prev_permutation is one of them. We can enumerate the digits easily thanks to the rich STL.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: string largestTimeFromDigits(vector<int>& A) { sort(begin(A), end(A)); string ans = getTime(A); while (next_permutation(begin(A), end(A))) { auto time = getTime(A); if ((!time.empty()) && (time > ans)) { ans = time; } } return ans; } private: string getTime(vector<int>& A) { int hour = A[0] * 10 + A[1]; int minute = A[2] * 10 + A[3]; if ((hour > 23) || (minute >= 60)) return ""; return std::to_string(A[0]) + std::to_string(A[1]) + ":" + std::to_string(A[2]) + std::to_string(A[3]); } }; |
class Solution {
public:
string largestTimeFromDigits(vector<int>& A) {
sort(begin(A), end(A));
string ans = getTime(A);
while (next_permutation(begin(A), end(A))) {
auto time = getTime(A);
if ((!time.empty()) && (time > ans)) {
ans = time;
}
}
return ans;
}
private:
string getTime(vector<int>& A) {
int hour = A[0] * 10 + A[1];
int minute = A[2] * 10 + A[3];
if ((hour > 23) || (minute >= 60)) return "";
return std::to_string(A[0]) +
std::to_string(A[1]) + ":" +
std::to_string(A[2]) +
std::to_string(A[3]);
}
};We can actually replace the if check in the while loop with the following:
1 | ans = max(ans, time); |
ans = max(ans, time);
In order to do a full permutation cycle – we have to sort the array. The complexity is also O(1) constant since the array size is fixed to four.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Use Hash Map to Count the Frequencies of Values and Iterate the Key-Value Pairs in AWK?
Next Post: Algorithms to Compute the Dot Product of Two Sparse Vectors
