This is the 21st day of my participation in the genwen Challenge

Topic describes

The binary watch has four leds at the top representing hours (0-11) and six leds at the bottom representing minutes (0-59). Each LED represents a 0 or 1, with the lowest being on the right.

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

Give you an integer turnedOn, which represents the number of leds that are currently on, and turnedOn returns all the possible times that the binary watch can represent. You can return the answers in any order.

Hours do not begin with zero:

For example, “01:00” is an invalid time. The correct writing would be “1:00”.

Minutes must consist of two digits, which may start with zero:

For example, “10:2” is an invalid time. The correct way to write it is “10:02”.

Example 1:

Input: turnedOn = 1 output: [" 0:01, "" 0:02", "0:04", "0:08", "0:16", "0:32", "notes", "2", "4:00 PM," "8"]Copy the code

Example 2:

TurnedOn = 9 turnedOn: []Copy the code

Tip:

  • 0 < =turnedOn< = 10

Their thinking

Idea 1: Enumeration time

Hours are represented by four bits and minutes by six bits. A bit value of 0 indicates that the indicator is off and a bit value of 1 indicates that the indicator is on.

We can enumerateall the possible values for hour [0,11][0,11][0,11] and all the possible values for minute [0,59][0,59][0,59] [0,59] and calculate the sum of the number of 1s in the binary of both turnedOn, and add it to the answer, if turnedOn

C + + code

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                    ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m)); }}}returnans; }};Copy the code

Idea 2: Enumerate seconds

Another enumeration method is to enumerate all 210=10242^{10}=1024210=1024 combinations of lights on and off, that is, a binary number to represent the lights on and off, its high four bits for hours, low six bits for minutes. If the values of hour and minute are within the turnedOn legal range, and the number of 1 in the binary is turnedOn, add it to the answer

C + + code

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int i = 0; i < 1024; ++i) {
            int h = i >> 6, m = i & 63; // Use the bit operation to fetch the high 4 bits and low 6 bits
            if (h < 12 && m < 60 && __builtin_popcount(i) == turnedOn) {
                ans.push_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m)); }}returnans; }};Copy the code