Let's design a clock. This clock has a format of (hour: miniutes). Lets use bit to represent it.
For example,
10: 15 is represented as 1010:1111.
Question: given n as total number of bit that is 1, print all the possible clock time. (eg, in the 10:15 example, n = 6, but I am asking you to print all the other possible configuration that also has six bit 1 ).
My attempt: I stored hours into a 5-element vector (max 24). And minutes into a 6-element vector (max 60). And then I divide n into two numbers: n = n-i, i, for i in the [0, n].
The former n-i represent number of 1s bit to turn on for hour vector, the latter i represents number of 1s bit to turn on for the minute vector. Then you can use next_permutation to get the next ordering of the vector (given that they have same number of 1s).
However, this is more like a brute force solution. I am wondering if you guys have better algorithms in mind?
class Solution5 {
public:
void print_clock (int n) {
if (n == 0) {cout<<"0"<<endl; return;}
vector<vector<int>> res;
vector<int> hour (5, 0);
vector<int> min (6, 0);
for (int i=0; i< n; i++)
rec_print(n - i, i, res, hour, min);
cout<<endl<<"completed"<<endl;
}
void rec_print (int h, int m, vector<vector<int>> & res, vector<int> hour, vector<int> min) {
if (h > 5 || m > 6) return;
int z = hour.size() -1;
while (h-- > 0) hour[z--] = 1;
z = min.size() -1;
//vector<int> hour = {0,0,1,1,1};
while (m-- > 0) min[z--] = 1;
//while(next_permutation(hour.begin(), hour.end()) )
// cout<<"he";
while (get_vector(h, hour, 24) ) {
vector<int> tmp = min;
while (get_vector(m, tmp, 60)) {
cout<<"hour : ";
for (int i=0 ; i<hour.size(); i++)
cout<<hour[i];
cout<<endl<<"miniutes : ";
for (int i=0; i<min.size(); i++)
cout<<min[i];
cout<<endl<<"---------------"<<endl;
if(next_permutation(tmp.begin(), tmp.end()) == 0 ) break;
}
if (next_permutation(hour.begin(), hour.end())== 0) break;
}
//cout<<endl<<"completed"<<endl;
}
bool get_vector (int n, vector<int> & tmp, int maxi) {
int sum = 0;
for (int i = tmp.size() - 1; i >=0; i--) {
sum += tmp[i] * pow(2,tmp.size() -1 - i);
if (sum > maxi)
return false;
}
return true;
}
