Read binary watch

XXX. Read Binary Watch

Backtracking

Bit Manipulation

Problem Statement:

A binary watch has 4 LEDs for the hours (0-11) and 6 LEDs for the minutes (0-59). Each LED represents a power of two. Given the number of LEDs that are currently on, return all possible times the watch could represent.

Algorithm:

The algorithm uses backtracking to explore all possible combinations of LEDs that can be turned on to represent a valid time:

1. Use a backtracking helper function to explore combinations of LEDs.
2. For each combination:
   • Calculate the hours and minutes represented by the current LED combination.
   • Ensure the hours are between 0 and 11, and the minutes are between 0 and 59.
3. If the combination is valid, format it as "hours:minutes" and add it to the result list.

Complexity:

Time Complexity: O(2^n), where n is the number of LEDs (10). Each subset of LEDs is explored.
Space Complexity: O(n), for the recursion stack and temporary variables.

Java Implementation:

class Solution {
    public List readBinaryWatch(int num) {
        int[] subset = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32}; // LED values for hours and minutes
        List result = new ArrayList<>();
        backtrack(result, subset, 0, 0, num, 0);
        Collections.sort(result); // Sort the results lexicographically
        return result;
    }

    public void backtrack(List result, int[] subset, int hours, int minutes, int LEDs, int start) {
        if (minutes >= 60 || hours >= 12) return; // Invalid time

        if (LEDs == 0) { // All LEDs have been used
            addTime(hours, minutes, result);
            return;
        }

        for (int i = start; i < subset.length; i++) {
            if (i <= 3) hours += subset[i]; // Use LED for hours
            else minutes += subset[i]; // Use LED for minutes

            backtrack(result, subset, hours, minutes, LEDs - 1, i + 1); // Recurse

            if (i <= 3) hours -= subset[i]; // Undo hour addition
            else minutes -= subset[i]; // Undo minute addition
        }
    }

    public void addTime(int hours, int minutes, List result) {
        StringBuilder sb = new StringBuilder();
        sb.append(hours).append(":");
        if (minutes < 10) sb.append(0); // Add leading zero for minutes
        sb.append(minutes);
        result.add(sb.toString()); // Add formatted time to the result
    }
}