Leetcode Binary Watch problem solution

YASH PAL,

In this Leetcode Binary Watch problem solution, 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. Given an integer turnedOn which represents the number of LEDs that are currently on, return all possible times the watch could represent. You may return the answer in any order.

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”.

Leetcode Binary Watch problem solution

Problem solution in Python.

from collections import defaultdict
class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        hours = self.countones('h')
        minutes = self.countones('m')

        # set of times that have 1's = num
        result = set()
        
        for h in range(num+1):
            m = num - h
            
            for hour in hours[h]:
                for minute in minutes[m]:
                    strhour = str(hour)
                    strminute = "0"+str(minute) if minute < 10 else str(minute)
                    result.add(strhour+':'+strminute)
        
        return list(result)
        
        
    def countones(self, _type: str) -> dict[int]:
        # mapping of numbers that count of ones -> numbers that have the count
        ones = defaultdict(list)
        
        # hours
        if _type == 'h':
            for i in range(12):
                count = self.numberofones(i)
                ones[count].append(i)
        
        # minutes
        else:
            for i in range(60):
                count = self.numberofones(i)
                ones[count].append(i)
        return ones
    
    # function to count the number of 1s in binary representation
    def numberofones(self, number: int) -> int:
        count = 0
        while(number > 0):
            rem =  number % 2
            number = number // 2
            if rem == 1:
                count += 1
        return count

Problem solution in Java.

class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> result = new ArrayList<>();
        for (int hh = 0; hh < 12; hh++)
            for (int mn = 0; mn < 60; mn++)
                if (aux(hh, mn, num))
                    if (mn < 10)
                        result.add(String.format("%d:0%d", hh, mn));
                    else
                        result.add(String.format("%d:%d", hh, mn));
        return result;    
    }
    private boolean aux(int hh, int mn, int num){
        int temp = 0;
        while(hh != 0 || mn != 0){
            if (hh !=0 ){
                temp += hh % 2;
                hh /=2;
            }
            if (mn != 0){
                temp += mn % 2;
                mn /= 2;
            }
        }
        return temp == num;
    }
}

Problem solution in C++.

vector<string> readBinaryWatch(int num) {
        union {
            struct {
                unsigned hours:4;
                unsigned minutes:6;
            };
            unsigned all;
        } time {0};

        vector<string> result;
        function<void(int, int)> place = [&](int n, int ifrom) {
            if (n == 0) {
                if (time.hours < 12 and time.minutes < 60) {
                    char buf[20];
                    sprintf(buf, "%d:%02d", time.hours, time.minutes);
                    result.push_back(string(buf));
                }
            } else {
                for (int i = ifrom; i < 10; ++i) {
                    if (!(time.all >> i & 1)) {
                        time.all |= 1 << i;
                        place(n - 1, i);
                        time.all &= ~(1 << i);
                    }
                }
            }
        };
        place(num, 0);
        return result;
    }

Problem solution in C.

int count_ones(int n)
{
    int count=0;
    while(n)
    {
        n = n & (n-1);
        count++;
    }
    return count;
}

char** readBinaryWatch(int num, int* returnSize)
{
    char **ans = malloc(sizeof(char *) * 1024);
    int ret_count=0;
        
    for(int h=0;h<12;h++)
    {
        for(int m=0;m<60;m++)
        {
            int tmp = (h<<6)|m;
            if(count_ones(tmp)==num)
            {                
                char *tmp = malloc(sizeof(char)*6);
                sprintf(tmp,"%d:%02d",h%12,m%60);
                ans[ret_count++] = tmp;
            }
        }
    }
    *returnSize=ret_count;
    return ans;
}

coding problems