Binary Watch Problem

Title: Binary Watch Source: leetcode.com

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.

Binary Watch reading

A Binary Watch reading time: “3:25”.

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

Input: n=1
Output: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

Solution

First thing to note about the problem is about the possible values we can have for n.
If we see the hours section of Watch, we have 4 LEDs. However, we can’t have all 4 in ON state simultaneously as it would make hour value to be more than 12 while the problem specifies hour values to be only in range 0-11.

Similarly, for minutes, we can’t have a value more than 59.
Next we need to have a way of making combinations similar to nCr (Choosing r values out of given n).

Python solution

Binary Watch Problem
Rate this post

Leave a Reply