Count the Binary Watch Stats using Bruteforce Algorithm via C++ BitSet or Compiler Intrinsics __builtin_popcount

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.

A Binary Watch

For example, the above binary watch reads “3:25”.

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

Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]
Note:
The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Bruteforce Algorithm in O(1)

Given two candidate arrays we can choose up to Num from, we can use Depth First Search algorithm to select the possible combination. However, the implementation would be non-trivial and a bit lengthy and complex.

The given hours and minutes stats are limited, therefore, we can bruteforce the hours from 0 to 11, the minutes from 0 to 59, which results in an O(1) bruteforce algorithm. The numbers are checked for the bits that are set.

We can use the C++ compiler Intrinsics __builtin_popcount(num) or the C++ std::bitset<bits>(num).count() to compute the number of 1-bits in the num binary, which simulates perfect for the binary watch stats.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> r;
        if ((num < 0)) {
            return r;
        }
        for (int h = 0; h < 12; ++ h) {
            for (int m = 0; m < 60; ++ m) {
                // hour is fit into 4-bits (max 15)
                if (bitset<16>((m << 4) + h).count() == num) {
                // or using compiler Intrinsics
                // if (__builtin_popcount(h) + __builtin_popcount(m) == num) {
                    string s = std::to_string(h);
                    s += ":";
                    if (m < 10) s += "0";
                    s += std::to_string(m);
                    r.push_back(s);
                }
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> r;
        if ((num < 0)) {
            return r;
        }
        for (int h = 0; h < 12; ++ h) {
            for (int m = 0; m < 60; ++ m) {
                // hour is fit into 4-bits (max 15)
                if (bitset<16>((m << 4) + h).count() == num) {
                // or using compiler Intrinsics
                // if (__builtin_popcount(h) + __builtin_popcount(m) == num) {
                    string s = std::to_string(h);
                    s += ":";
                    if (m < 10) s += "0";
                    s += std::to_string(m);
                    r.push_back(s);
                }
            }
        }
        return r;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —