401. Binary Watch

Description

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.

Intuition

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.

Approach

1. Iterate over all possible hours (0-11) and minutes (0-59).
2. Convert each hour and minute to its binary representation.
3. Count the number of "1"s (set bits) in the binary representation of the hour and minute.
4. If the sum of set bits matches the given number of LEDs, format the time as "hour:minute" and add it to the result.
5. Return the list of all valid times.

Complexity

Time Complexity:

O(12 * 60), as we iterate over all possible hours (12 values) and minutes (60 values).

Space Complexity:

O(1) for constant space, ignoring the output list size.

Code

C++

class Solution {
public:
    std::vector readBinaryWatch(int num) {
        std::vector 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;
    }
};

Python

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

Java

public class Solution {
    public List readBinaryWatch(int num) {
        List 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;
    }
}

JavaScript

/**
 * @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;
};