Leetcode – Binary Watch Solution in Python

Spread the love

Introduction

In this comprehensive article, we will explore the ‘Binary Watch’ problem on Leetcode, discuss multiple approaches to solve it in Python, analyze the time complexity, and understand the concepts involved.

Problem Statement

The ‘Binary Watch’ problem is listed as problem number 401 on Leetcode. The problem statement is as follows:

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.

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.

Example:

Input: turnedOn = 1
Output: ["1:00","2:00","4:00","8:00","0:01","0:02","0:03","0:04","0:08","0:16","0:32"]

Approach 1: Bit Manipulation

  1. There are 10 LEDs in total. For each number from 0 to 1023 (2^10 – 1), use bit manipulation to count the number of set bits.
  2. If the number of set bits equals turnedOn, check if it represents a valid time.
  3. To get the hours, right shift the number by 6 positions.
  4. To get the minutes, use bitwise AND operation with 0x3F (0011 1111 in binary) to get the last 6 bits.
  5. Validate the hours and minutes. If they are valid, convert them into the format “H:MM” and add it to the result list.
def readBinaryWatch(turnedOn):
    def bitCount(n):
        # Counts the number of set bits in binary representation of n
        return bin(n).count('1')
    
    result = []
    for n in range(1024):  # 2^10
        if bitCount(n) == turnedOn:
            # Extract hours and minutes
            hours, minutes = n >> 6, n & 0x3F
            # Validate and format
            if hours < 12 and minutes < 60:
                result.append(f"{hours}:{minutes:02d}")
    return result

Time Complexity

The time complexity of this approach is O(1) because the loop runs a constant number of times (1024).

Approach 2: Backtracking

  1. Use backtracking to turn on LEDs and keep track of the number of LEDs turned on for hours and minutes.
  2. If the total number of LEDs turned on equals turnedOn, validate if the time is valid.
  3. Convert the binary representation of hours and minutes to decimal and add them to the result in the format “H:MM”.
def readBinaryWatch(turnedOn):
    def backtrack(start, hours, minutes, turnedOn):
        if turnedOn == 0:
            if hours < 12 and minutes < 60:
                result.append(f"{hours}:{minutes:02d}")
            return
        
        for i in range(start, 10):
            if i < 4:
                backtrack(i + 1, hours + (1 << i), minutes, turnedOn - 1)
            else:
                k = i - 4
                backtrack(i + 1, hours, minutes + (1 << k), turnedOn - 1)

    result = []
    backtrack(0, 0, 0, turnedOn)
    return result

Time Complexity

The time complexity of this approach is O(2^N) where N is the number of LEDs, as it explores each combination through backtracking.

Conclusion

The ‘Binary Watch’ problem on LeetCode can be addressed using various algorithms, including bit manipulation and backtracking. Understanding these different approaches is not only helpful for solving this particular problem but can also be applied to various other combinatorial problems. It’s essential to choose the approach that is most suitable depending on the constraints and requirements of your specific situation. The bit manipulation approach is more efficient for this problem as it has constant time complexity, while the backtracking approach provides a deeper understanding of combinatorial possibilities.

Leave a Reply