C++ 0ms bit manipulation


  • 1
    H

    There are total 10 bits to present a time. We can use high 4 bits as hour and low 6 bits as minutes. It is easy to figure out that the maximum value of num is 8, or the either hour or minute will overflow.
    So, iterate all numbers from 0 to 0x2FF (1011 | 111111), 1011 is 11.

    class Solution {
    public:
        vector<string> readBinaryWatch(int num) {
            vector<string> res;
            if (num < 0 || num > 8) return res;
            for (int i = 0; i < 0x2FF; i++) {
                if (bitset<16>(i).count() == num) add(i, res);
            }
            return res;
        }
        
        void add(int n, vector<string>& res) {
            string s;
            int mins = n & 0x3F;
            if (mins > 59) return;
            int hour = n >> 6 & 0xF;
            if (hour > 11) return;
            s += to_string(hour) + ":";
            if (mins < 10) s += "0";
            s += to_string(mins);
            res.push_back(s);
        }
    };
    

    Inspired by @StefanPochmann's idea. Below is the C++ version

    class Solution {
    public:
        vector<string> readBinaryWatch(int num) {
            vector<string> res;
            if (num < 0 || num > 8) return res;
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 60; j++) {
                    if (bitset<16>((j << 4) + i).count() == num) {
                        string t = to_string(i) + ":";
                        if (j < 10) t.push_back('0');
                        t += to_string(j);
                        res.push_back(t);
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.