Binary Watch

Problem

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

Solution

public class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == num) res.add(String.format("%d:%02d", h, m));
            }
        }
        return res;
    }

    //Here is a simple implementation of bitCount(), in case Integer.bitCount() not allowed to use in the interview
    private int bitCount(int n) {
        int res = 0;
        while (n > 0) {
            res += n % 2;
            n /= 2;
        }
        return res;
    }
}

Analysis

The problem asks how many situations can be found by given number of lights
The solution, however, uses the opposite direction to get the correct result
That is, we loop through all time of hour and minute
Then we get the sum of their bitCount and compare it the given num
If they are same, we add that time into our list
Notice how we format the time by using String.format()
02%d means to use two digits and start with 0 if it's a single digit number