Dare2Solve
The problem is to determine the possible times displayed on a binary watch, where a certain number of LEDs are turned on. A binary watch has four LEDs to represent hours (0-11) and six LEDs to represent minutes (0-59). Given a number of LEDs that are on, the task is to return all possible valid times the watch can display.
The binary representation of hours and minutes on a binary watch can be used to count the number of "1"s (on LEDs). For each possible hour (0-11) and minute (0-59), we can count the number of "1"s in their binary representations. If the sum of "1"s for both the hour and minute equals the given number of LEDs, it is a valid time.
O(12 * 60), as we iterate over all possible hours (12 values) and minutes (60 values).
O(1) for constant space, ignoring the output list size.
class Solution {
public:
std::vector<std::string> readBinaryWatch(int num) {
std::vector<std::string> times;
for (int h = 0; h < 12; ++h) {
for (int m = 0; m < 60; ++m) {
int hOnes = std::bitset<4>(h).count();
int mOnes = std::bitset<6>(m).count();
if (hOnes + mOnes == num) {
times.push_back(std::to_string(h) + ":" + (m < 10 ? "0" : "") + std::to_string(m));
}
}
}
return times;
}
};
class Solution:
def readBinaryWatch(self, num: int) -> list[str]:
times = []
for h in range(12):
for m in range(60):
hOnes = bin(h).count('1')
mOnes = bin(m).count('1')
if hOnes + mOnes == num:
times.append(f"{h}:{m:02d}")
return times
public class Solution {
public List<String> readBinaryWatch(int num) {
List<String> times = new ArrayList<>();
for (int h = 0; h < 12; h++) {
for (int m = 0; m < 60; m++) {
int hOnes = Integer.bitCount(h);
int mOnes = Integer.bitCount(m);
if (hOnes + mOnes == num) {
times.add(h + ":" + (m < 10 ? "0" : "") + m);
}
}
}
return times;
}
}
/**
* @param {number} num
* @return {string[]}
*/
var readBinaryWatch = function (num) {
const times = [];
for (let h = 0; h < 12; h++) {
for (let m = 0; m < 60; m++) {
const hOnes = h ? h.toString(2).match(/1/g).length : 0;
const mOnes = m ? m.toString(2).match(/1/g).length : 0;
if (hOnes + mOnes === num) {
times.push(`${h}:${m < 10 ? `0${m}` : m}`);
}
}
}
return times;
};