In C++, Given four digits, find the maximum valid time that can be displayed on
ID: 3829352 • Letter: I
Question
In C++, Given four digits, find the maximum valid time that can be displayed on a digital clock (in 24-hour format) using those digits.
For example, given digits 1,8,3,2 the maximum valid time is "23:18". Note that "28:31" is not a valid time.
Try to achieve O(n) if possible rather than O(n^2) solution.
Write a function:
-string MaxTime(int A, int B, int C, int D); that, given four integers A,B,C,D, returns the maximum valid time in string format "HH:MM" or "NOT POSSIBLE" if it is not possible to display a valid time.
Examples: given 1,8,3,2, the function MaxTime shoud return "23:18".
Given 2,4,0,0 the funtion should return "20:40".
Given 3,0,7,0 the function should return "07:30"
Given 9,1,9,7 the function should return "NOT POSSIBLE". Since there is no possible valid time.
Assume that: A,B,C,D are integers with in the range [0..9]
Explanation / Answer
#include <iostream>
using namespace std;
int main()
{
int a[4];
bool valid[4] = { true, true,true,true };
int hour = 0;
int minute = 0;
bool success = false;
cin >> a[0] >> a[1] >> a[2] >> a[3];
for (int h = 24; h > 0; h--)
{
for (int i = 0; i < 4; i++)
{
if (h / 10 == a[i] && valid[i])
{
valid[i] = false;
for (int j = 0; j < 4; j++)
{
if (h % 10 == a[j] && valid[j])
{
valid[j] = false;
hour = a[i] * 10 + a[j];
success = true;
break;
}
}
if (success != true)
{
valid[i] = true;
}
else
{
break;
}
}
}
if (success == true)
{
success = false;
break;
}
}
for (int m = 60; m > 0; m--)
{
for (int i = 0; i < 4; i++)
{
if (m / 10 == a[i] && valid[i])
{
valid[i] = false;
for (int j = 0; j < 4; j++)
{
if (m % 10 == a[j] && valid[j])
{
valid[j] = false;
minute = a[i] * 10 + a[j];
success = true;
break;
}
}
if (success != true)
{
valid[i] = true;
}
else
{
break;
}
}
}
if (success == true)
{
success = false;
break;
}
}
if ((valid[0] || valid[1] || valid[2] || valid[3]) != false)
{
}
else
{
cout << hour << ":" << minute;
}
return 0;
}