A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.
For example, the above binary watch reads "3:25".
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:
Input: n = 1 Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"] Note: The order of output does not matter. The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00". The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".
public class Solution {
public IList<string> ReadBinaryWatch(int num) {
var res = new List<string>();
for(int i=0;i<12;i++){
for(int j=0;j<60;j++){
if(NumberOfSetBits(i)+NumberOfSetBits(j)==num){
res.Add(i+":"+((j<10)?"0":"")+j);
}
}
}
return res;
}
private int CountBits(int num){
int count = 0;
while (num != 0)
{
count++;
num &= num - 1;
}
return count;
}
private int NumberOfSetBits(int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
}Time Complexity: O(1) // since minutes and hours are constant.
Space Complexity: O(1)
