401. Binary Watch – Leetcode Solutions

Example 1:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

Input: turnedOn = 9
Output: []

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # List to store all possible times
        results = []
        
        # Loop through all possible hours (0-11)
        for hour in range(12):
            # Loop through all possible minutes (0-59)
            for minute in range(60):
                # Count the total number of LEDs turned on
                if bin(hour).count('1') + bin(minute).count('1') == turnedOn:
                    # Format the time as "hour:minute" with proper zero padding for minutes
                    results.append(f"{hour}:{minute:02d}")
        
        # Return all valid times
        return results

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> result; // Stores all valid times
        // Iterate over all possible hours (0-11)
        for (int hour = 0; hour < 12; ++hour) {
            // Iterate over all possible minutes (0-59)
            for (int minute = 0; minute < 60; ++minute) {
                // Count the total number of LEDs turned on
                int count = bitset<10>(hour << 6 | minute).count();
                if (count == turnedOn) {
                    // Construct the time string in "h:mm" or "h:0m" format
                    result.push_back(to_string(hour) + ":" + (minute < 10 ? "0" : "") + to_string(minute));
                }
            }
        }
        return result;
    }
};

var readBinaryWatch = function(turnedOn) {
    // Initialize an array to store all possible valid times
    let result = [];

    // Loop through all possible hour values (0 to 11)
    for (let hour = 0; hour < 12; hour++) {
        // Loop through all possible minute values (0 to 59)
        for (let minute = 0; minute < 60; minute++) {
            // Calculate the total number of LEDs turned on for this hour and minute
            let ledCount = countBits(hour) + countBits(minute);

            // If the total number of LEDs matches the input `turnedOn`, it's a valid time
            if (ledCount === turnedOn) {
                // Format the time as "hour:minute" (minute should be two digits)
                let time = `${hour}:${minute.toString().padStart(2, '0')}`;
                result.push(time);
            }
        }
    }

    // Return the array of valid times
    return result;
};

function countBits(num) {
    let count = 0;
    while (num > 0) {
        count += num & 1; // Check if the last bit is 1
        num >>= 1;        // Right-shift to remove the last bit
    }
    return count;
}

class Solution {
    /**
     * Returns all possible times a binary watch can represent with a given number of LEDs turned on.
     *
     * @param turnedOn The number of LEDs that are currently on.
     * @return A list of possible times as strings in "H:MM" format.
     */
    public List<String> readBinaryWatch(int turnedOn) {
        // List to store all possible valid times.
        List<String> result = new ArrayList<>();
        
        // Iterate over all possible hour (0 to 11) and minute (0 to 59) combinations.
        for (int hour = 0; hour < 12; hour++) {
            for (int minute = 0; minute < 60; minute++) {
                // Count the number of bits that are set to 1 in the binary representation of hour and minute.
                if (Integer.bitCount(hour) + Integer.bitCount(minute) == turnedOn) {
                    // Format the time string as "H:MM" and add it to the result list.
                    result.add(String.format("%d:%02d", hour, minute));
                }
            }
        }
        
        return result;
    }
}