Time Cost

10min11s

Implementation

There are two solutions to solve this problem. The first solution came out my mind is using recursive function and a visited vector to record visited bits. In the second solution, we iterate all valid times directly which is way faster than the first solution. Note that there’s a useful non-standard built-in function called __builtin_popcount which we can get the bit number of an integer.

Code

• Solution 1 (recursive)

  class Solution {
    vector<int> nums = {8,4,2,1,32,16,8,4,2,1};
  public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> result;
        vector<bool> ison(10, false);
        recur(result, ison, turnedOn, 0);
        return result;
    }
  
    void recur(vector<string>& result, vector<bool>& ison, int turnedOn, int index) {
        if (index == 10) {
            if (turnedOn == 0) {
                // equal than 0
                int hour = 0, minute = 0;
                for (int i=0; i<10; i++) {
                    if (ison[i]) {
                        if (i <= 3) {
                            hour += nums[i];
                        }else{
                            minute += nums[i];
                        }
                    }
                }
  
                if (hour < 12 && minute <= 59) {
                    // valid
                    string str = to_string(hour) + ":";
                    if (minute < 10) {
                        str = str + "0" + std::to_string(minute);
                    }else{
                        str = str + std::to_string(minute);
                    }
                    result.push_back(str);
                }
            }
            return;
        }
        if (turnedOn > 0) {
            recur(result, ison, turnedOn, index+1);
            ison[index] = true;
            recur(result, ison, turnedOn-1, index+1);
            ison[index] = false;
        }else{
            // equal than 0
            int hour = 0, minute = 0;
            for (int i=0; i<10; i++) {
                if (ison[i]) {
                    if (i <= 3) {
                        hour += nums[i];
                    }else{
                        minute += nums[i];
                    }
                }
            }
  
            if (hour < 12 && minute <= 59) {
                // valid
                string str = to_string(hour) + ":";
                if (minute < 10) {
                    str = str + "0" + std::to_string(minute);
                }else{
                    str = str + std::to_string(minute);
                }
                result.push_back(str);
            }
        }
    }
  };
  

• Solution 2 (O(n) = c)

  class Solution {
  public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> result;
          
        // 720
        for (int h=0; h<12; h++) {
            for (int m=0; m<60; m++) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    if (m < 10) {
                        result.push_back(std::to_string(h) + ":0" + std::to_string(m));
                    }else {
                        result.push_back(std::to_string(h) + ":" + std::to_string(m));
                    }
                }
            }
        }
  
        return result;
    }
  };