algoadvance

Leetcode 401. Binary Watch

Problem Statement:

A binary watch has 4 LEDs to represent the hours (0 to 11) and 6 LEDs to represent the minutes (0 to 59). Each LED represents a bit that can either be 0 or 1.

For example, the binary representation of the time “3:25” would be:

• The hour “3” -> “0011”
• The minute “25” -> “011001”

Given a non-negative integer turnedOn which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Clarifying Questions:

1. What is the maximum value for turnedOn?
   • The maximum value for turnedOn is 10 because there are exactly 10 LEDs in total (4 for hours and 6 for minutes).
2. Should the times be returned in any specific order?
   • The times can be returned in any order.
3. Are there constraints on the format of the output?
   • The times should be formatted as “h:mm” where h does not have leading zeros and mm always has exactly two digits.

Strategy:

1. We need to generate all possible combinations of hours and minutes where the sum of bits turned on equals turnedOn.
2. Use two nested loops:
   • Outer loop for hours (from 0 to 11).
   • Inner loop for minutes (from 0 to 59).
3. For each combination, count the number of 1’s in their binary representations.
4. If the sum matches turnedOn, format the time and add it to the results.

Code:

#include <iostream>
#include <vector>
#include <string>
#include <bitset>

using namespace std;

vector<string> readBinaryWatch(int turnedOn) {
    vector<string> result;
    for (int hours = 0; hours < 12; ++hours) {
        for (int minutes = 0; minutes < 60; ++minutes) {
            // Count the number of 1s in hours and minutes.
            if (bitset<10>(hours).count() + bitset<10>(minutes).count() == turnedOn) {
                // Format the time as h:mm
                result.push_back(to_string(hours) + (minutes < 10 ? ":0" : ":") + to_string(minutes));
            }
        }
    }
    return result;
}

// Helper function to print the vector of strings
void printTimes(vector<string>& times) {
    for (const auto& time : times) {
        cout << time << " ";
    }
    cout << endl;
}

int main() {
    vector<string> times;
    int turnedOn = 1;

    // Test the function with turnedOn = 1
    times = readBinaryWatch(turnedOn);
    printTimes(times);

    return 0;
}

Time Complexity:

• The code uses two nested loops where:
  • The outer loop iterates from 0 to 11 (12 times).
  • The inner loop iterates from 0 to 59 (60 times).
• For each iteration, it counts the number of 1 bits using bitset, which takes constant time.

Therefore, the time complexity is O(1), considering the constant number of iterations (12 * 60 = 720).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?