Binary Watch – Bit Manipulation Instead of Backtracking

Binary Watch

A binary watch has:

• 4 LEDs for hours (0–11)
• 6 LEDs for minutes (0–59)

Each LED represents a binary digit (LSB on the right).

Given an integer turnedOn, return all possible valid times such that exactly turnedOn LEDs are on.

Constraints:

• Hour must not have a leading zero → "01:00" ❌, "1:00" ✅
• Minutes must always have two digits → "10:2" ❌, "10:02" ✅
• 0 <= turnedOn <= 10

---

My Thought Process

At first glance, this smelled like combinatorics.

We have 10 LEDs total (4 + 6), and we’re asked to turn on exactly k of them. My first instinct was:

“This is a combination / recursion / backtracking problem.”

Pick k LEDs out of 10, compute their numeric value, validate hour/minute, and collect results.

But then I noticed something important.

The minute LEDs represent:

1, 2, 4, 8, 16, 32

That’s literally:

2^0, 2^1, 2^2, 2^3, 2^4, 2^5

Same for hours:

1, 2, 4, 8

That’s just binary.

At that point, I paused.

The problem was labeled Easy. That was the signal. If this were meant to be recursion-heavy, it probably wouldn’t be categorized as Easy.

So instead of generating combinations of LEDs…

I inverted the thinking:

Instead of generating LED states → compute time Just generate all valid times → count how many LEDs are on

That’s much simpler.

---

The Key Insight

Every hour h (0–11) is already a 4-bit number. Every minute m (0–59) is already a 6-bit number.

So the number of LEDs turned on is simply:

Integer.bitCount(h) + Integer.bitCount(m)

If that equals turnedOn, it’s a valid answer.

No recursion. No backtracking. No combinations.

Just brute force.

---

Solution

class Solution {

    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<String>();

        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    ans.add(h + ":" + (m < 10 ? "0" : "") + m);
                }
            }
        }

        return ans;
    }
}

---

Why This Works

We iterate through:

• 12 possible hours
• 60 possible minutes

Total checks:

12 × 60 = 720

That’s constant.

So time complexity is:

O(12 × 60) → O(1)

Because the input range is fixed and bounded.

Space complexity depends on output size, but that’s unavoidable.

---

Performance

• Runtime: 6 ms (beats ~60%)
• Memory: 49 MB (beats ~33%)

There are more optimized or more memory-efficient versions, but this is already well within acceptable limits.

For an Easy problem, over-engineering it would be unnecessary.

---

Final Take Away

What I learned from this problem:

• Don’t jump into recursion just because something looks combinatorial.
• When the input space is tiny and bounded, brute force is often optimal.
• Bit manipulation can dramatically simplify logic when the domain is binary-based.
• Problem difficulty labels can be useful signals.

If I evaluate the conceptual difficulty: Once you see the bit trick → 2.5 / 10.

The tricky part isn’t implementation. It’s recognizing that you don’t need anything fancy.

Sometimes the best solution is just iterating over the whole state space and asking a very simple question.

And that’s it.