Binary Watch

Easy
730.

Binary Watch

Binary Watch is an easy coding problem on bit manipulation, backtracking and enumeration, asked in Amazon, Adobe and Oracle interviews.

A binary watch shows the hour with 4 LEDs (values 1, 2, 4, 8) and the minute with 6 LEDs (values 1, 2, 4, 8, 16, 32). Hours run from 0 to 11 and minutes from 0 to 59.

Given the number of LEDs that are lit, return every time the watch could be showing, formatted as "H:MM" — the hour without a leading zero and the minute always two digits.

List the times in increasing order of hour, then of minute.

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"]
Explanation
Exactly one LED is lit, so either one minute bit or one hour bit.

Example 2

Input
turnedOn = 9
Output
[]
Explanation
No valid time lights nine LEDs.

Example 3

Input
turnedOn = 0
Output
["0:00"]

Constraints

  • 0 <= turnedOn <= 10
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} turnedOn
 * @return {string[]}
 */
var readBinaryWatch = function(turnedOn) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Watch — Solution in Python, Java & C++

Binary Watch solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.

Binary Watch is an easy coding problem on bit manipulation, backtracking and enumeration, asked in Amazon, Adobe and Oracle interviews.

Problem statement

A binary watch shows the hour with 4 LEDs (values 1, 2, 4, 8) and the minute with 6 LEDs (values 1, 2, 4, 8, 16, 32). Hours run from 0 to 11 and minutes from 0 to 59.

Given the number of LEDs that are lit, return every time the watch could be showing, formatted as "H:MM" — the hour without a leading zero and the minute always two digits.

List the times in increasing order of hour, then of minute.

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"]
Explanation: Exactly one LED is lit, so either one minute bit or one hour bit.

Example 2

Input: turnedOn = 9
Output: []
Explanation: No valid time lights nine LEDs.

Example 3

Input: turnedOn = 0
Output: ["0:00"]

Constraints

  • 0 <= turnedOn <= 10

Hints for Binary Watch

  1. Hint 1

    There are only 12 × 60 = 720 possible times — just try them all.

  2. Hint 2

    For each, count the set bits of the hour and the minute and compare with turnedOn.

  3. Hint 3

    The minute needs zero padding to two digits; the hour does not.

How to solve Binary Watch

The search space is tiny, so enumerate every legal time and keep the ones whose total popcount matches.

Approach

  1. Loop h from 0 to 11 and m from 0 to 59.
  2. If popcount(h) + popcount(m) == turnedOn, format the time and collect it.
  3. The nested loop order already yields hour-then-minute ordering.

Why it works

Every reachable display corresponds to exactly one (h, m) pair, and the lit LEDs are exactly the set bits of the two numbers — so the popcount sum is the number of lit LEDs.

Complexity

  • Time — O(720)
  • Space — O(output)

Pitfalls

  • Forgetting to zero-pad the minute produces "1:0" instead of "1:00".
  • Padding the hour as well produces "01:00", which the format does not use.
  • Enumerating LED subsets instead of times is more work and risks duplicates.

Reference solution

Python

from typing import List

def readBinaryWatch(turnedOn: int) -> List[str]:
    out = []
    for h in range(12):
        for m in range(60):
            if bin(h).count("1") + bin(m).count("1") == turnedOn:
                out.append("{}:{:02d}".format(h, m))
    return out

Java

public static String[] readBinaryWatch(int turnedOn) {
    List<String> out = new ArrayList<>();
    for (int h = 0; h < 12; h++) {
        for (int m = 0; m < 60; m++) {
            if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                out.add(h + ":" + (m < 10 ? "0" + m : String.valueOf(m)));
            }
        }
    }
    return out.toArray(new String[0]);
}

C++

vector<string> readBinaryWatch(int turnedOn) {
    vector<string> out;
    for (int h = 0; h < 12; h++) {
        for (int m = 0; m < 60; m++) {
            if (__builtin_popcount((unsigned) h) + __builtin_popcount((unsigned) m) == turnedOn) {
                string mm = to_string(m);
                if (m < 10) mm = "0" + mm;
                out.push_back(to_string(h) + ":" + mm);
            }
        }
    }
    return out;
}

JavaScript

var readBinaryWatch = function(turnedOn) {
    var bits = function(x) {
        var c = 0;
        while (x > 0) { c += x & 1; x >>= 1; }
        return c;
    };
    var out = [];
    for (var h = 0; h < 12; h++) {
        for (var m = 0; m < 60; m++) {
            if (bits(h) + bits(m) === turnedOn) {
                out.push(String(h) + ":" + (m < 10 ? "0" + String(m) : String(m)));
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation · Backtracking