Leetcode 401: Binary Watch

Image credit: Veri Ivanova from Unsplash

“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:

Problem is simple to understand. We get “num” as an argument and we have to find out all the possible times which can be formed using this.

With input value num as 1 we can generate

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

Now, let’s try to formulate the solution.

We have to find all the possible places where we can set the bit. Hour bit can be set to 1/2/4/8. Minute bit can be set to 1/2/4/8/16/32.

If we have num as 2, more combinations are possible. So, trying to solve the problem in straightforward way looks a bit complicated. So, let’s think of another approach.

1. Iterate over all the possible hour and minute options.
2. For each option, find the number of set bits in hour and minute.
3. If the “number of set bit” is equal to “num” — bingo! We have found a candidate. Find all such candidates and add them to a list.

public List<String> readBinaryWatch(int num) {
        
        List<String> ans = new ArrayList<>();
        
        
        // Hours iterate from 0-11 and
        // Minutes iterate from 0-59.
 
        // See for which values, number of 1's match
        // with the value <num> provided.
        
       for(int h=0; h<12; h++) {
            
           for(int m=0; m<60; m++) {
                
                // Number of set bits in hour portion and in minute
                // part has to be equal to num.
                if(Integer.bitCount(h) 
                                  + Integer.bitCount(m) == num) {
                    ans.add(String.format("%d:%02d",h,m));
                }
                
            }
            
        }
        
        return ans;
    }

Time complexity: O(1)

Space complexity: O(1)