algoadvance

Leetcode 401. Binary Watch

Problem Statement

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 a non-negative 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.

The hour (0-11) and minute (0-59) should be represented as a digital clock time of “HH:MM”.

Example

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

Clarifying Questions

  1. Is the input turnedOn always valid such that 0 <= turnedOn <= 10?
    • Yes, turnedOn will always be within this range.
  2. Can we assume the returned list of times does not need to be sorted?
    • Yes, the order of the output time strings does not matter.

Strategy

  1. Bit Counting:
    • For each possible combination of hour and minute, count the number of LEDs that are turned on.
    • We need to ensure the total number of turned-on LEDs equals turnedOn.
  2. Valid Time Checking:
    • We iterate from 0 to 11 for hours and from 0 to 59 for minutes.
    • Use bitwise operations to check how many bits are set (turned on) in these numbers.
  3. Format the Output:
    • Ensure the hour is a single or double digit and minute is two digits.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();
        
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                // Count the number of 1s in the binary representation of h and m
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    result.add(String.format("%d:%02d", h, m));
                }
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<String> times = solution.readBinaryWatch(1);
        for (String time : times) {
            System.out.println(time);
        }
    }
}

Time Complexity

Thus, the overall time complexity is O(12 * 60), which simplifies to O(720). Since 720 operations are quite manageable, the solution is efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI