Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Binary Watch

Explore how backtracking helps generate all possible valid times displayed by a binary watch based on a given number of LEDs turned on. Understand the recursive approach to check hours and minutes combinations, validate time constraints, and backtrack to explore alternative configurations. This lesson teaches the core technique for solving combinatorial problems using backtracking in coding interviews.

We'll cover the following...

Statement

A binary watch has 4 LEDs for displaying hours (ranging from 0 to 11) and 6 for displaying minutes (ranging from 0 to 59). Each LED can be on (1) or off (0), with the least significant bit on the right. For example, the binary watch below reads “9:22.”

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

Note: Remember the following regarding leading zeros:

  • The hour cannot have a leading zero (e.g., “01:00” is invalid, it should be “1:00”).

  • The minute must be two digits and may include a leading zero (e.g., “10:2” is invalid, it should be “10:02”).

Constraints:

  • 0≤0 \leq enabled ≤10\leq 10

Solution

The core intuition behind solving this problem is to use backtracking to explore all possible configurations of the LEDs that can be turned on. Because there are ...