Binary Watch - Practice Coding Problems

Binary Watch - Problem

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

Given an integer turnedOn which represents the number of LEDs that are currently on, return all possible times the watch could represent. You may return the answer in any order.

Format Requirements:

The hour must not contain a leading zero. For example, 01:00 is not valid. It should be 1:00.
The minute must consist of two digits and may contain a leading zero. For example, 10:2 is not valid. It should be 10:02.

Input & Output

Example 1 — One LED On

$ Input: turnedOn = 1

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

💡 Note: With 1 LED on, we can have hour 1,2,4,8 with minute 00 (binary: 1,10,100,1000 for hours), or hour 0 with minutes 1,2,4,8,16,32 (binary: 1,10,100,1000,10000,100000 for minutes)

Example 2 — No LEDs On

$ Input: turnedOn = 0

› Output: ["0:00"]

💡 Note: With no LEDs on, only 0:00 is possible (all bits are 0)

Example 3 — Many LEDs On

$ Input: turnedOn = 9

› Output: []

💡 Note: Maximum possible is 4+6=10 LEDs total. With hours max 11 (binary 1011 = 3 bits) and minutes max 59 (binary 111011 = 5 bits), we can't have 9 LEDs on simultaneously for any valid time

Constraints

0 ≤ turnedOn ≤ 10

Visualization

Tap to expand

Understanding the Visualization

LED Layout

4 LEDs for hours (0-11) and 6 LEDs for minutes (0-59)

Bit Counting

Count set bits in each valid hour and minute

Combination

Find pairs where total bits equals turnedOn

Key Takeaway

🎯 Key Insight: Convert the problem to counting set bits in binary representations

Asked in

G Google 25 a Amazon 20 Apple 15 M Microsoft 12

The key insight is to count the number of set bits (1s) in the binary representation of each possible hour and minute. The brute force approach checks all 720 possible times and filters those with the correct number of LEDs. Best approach uses bit counting for each hour-minute combination. Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Precompute Bit Counts	O(1)	O(1)	Precompute bit counts for all hours and minutes, then combine efficiently
Brute Force - Count Bits for All Times	O(1)	O(1)	Check every possible time (0:00 to 11:59) and count the total LED bits
Backtracking - Generate LED Combinations	O(2^10)	O(turnedOn)	Use backtracking to generate all ways to turn on exactly turnedOn LEDs

Optimized - Precompute Bit Counts — Algorithm Steps

Precompute bit counts for hours 0-11
Precompute bit counts for minutes 0-59
For each way to split turnedOn between hours and minutes
Combine all hour-minute pairs with matching bit counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Calculate bit counts for all hours and minutes once

Lookup

Use precomputed values instead of recalculating

Combine

Match hours and minutes with complementary bit counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countBits(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

char** solution(int turnedOn, int* returnSize) {
    // Precompute bit counts
    int hourBits[12], minuteBits[60];
    
    for (int i = 0; i < 12; i++) {
        hourBits[i] = countBits(i);
    }
    for (int i = 0; i < 60; i++) {
        minuteBits[i] = countBits(i);
    }
    
    char** result = malloc(1000 * sizeof(char*));
    *returnSize = 0;
    
    for (int hour = 0; hour < 12; hour++) {
        for (int minute = 0; minute < 60; minute++) {
            if (hourBits[hour] + minuteBits[minute] == turnedOn) {
                result[*returnSize] = malloc(10 * sizeof(char));
                sprintf(result[*returnSize], "%d:%02d", hour, minute);
                (*returnSize)++;
            }
        }
    }
    return result;
}

int main() {
    int turnedOn;
    scanf("%d", &turnedOn);
    
    int returnSize;
    char** result = solution(turnedOn, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Still processes same fixed number of hours and minutes

✓ Linear Growth

Space Complexity

O(1)

Precomputed arrays have fixed size (12 + 60 elements)

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Precompute Bit Counts — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler