401. Binary Watch

Problem Description

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

Given an integer turnedOn which represents the number of LEDs that are currently on, return all possible times the watch could represent. You may return the answer in any order.

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".

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: []

Constraints:

• 0 <= turnedOn <= 10

Python Solution

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        def count_bits(n: int) -> int:
            return bin(n).count('1')
        
        result = []
        # Try all possible hours and minutes
        for h in range(12):
            for m in range(60):
                # If total number of 1s equals turnedOn
                if count_bits(h) + count_bits(m) == turnedOn:
                    result.append(f"{h}:{m:02d}")
        
        return result

Java Solution

class Solution {
    private int countBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
    public List readBinaryWatch(int turnedOn) {
        List result = new ArrayList<>();
        
        // Try all possible hours and minutes
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                // If total number of 1s equals turnedOn
                if (countBits(h) + countBits(m) == turnedOn) {
                    result.add(String.format("%d:%02d", h, m));
                }
            }
        }
        
        return result;
    }
}

C++ Solution

class Solution {
private:
    int countBits(int n) {
        int count = 0;
        while (n) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
public:
    vector readBinaryWatch(int turnedOn) {
        vector result;
        
        // Try all possible hours and minutes
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                // If total number of 1s equals turnedOn
                if (countBits(h) + countBits(m) == turnedOn) {
                    result.push_back(to_string(h) + ":" + 
                                   (m < 10 ? "0" : "") + to_string(m));
                }
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    const countBits = (n) => {
        let count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    };
    
    const result = [];
    
    // Try all possible hours and minutes
    for (let h = 0; h < 12; h++) {
        for (let m = 0; m < 60; m++) {
            // If total number of 1s equals turnedOn
            if (countBits(h) + countBits(m) === turnedOn) {
                result.push(`${h}:${m.toString().padStart(2, '0')}`);
            }
        }
    }
    
    return result;
};

C# Solution

public class Solution {
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
    public IList ReadBinaryWatch(int turnedOn) {
        var result = new List();
        
        // Try all possible hours and minutes
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                // If total number of 1s equals turnedOn
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    result.Add($"{h}:{m:D2}");
                }
            }
        }
        
        return result;
    }
}