Blogs Hub

by Sumit Chourasia | Oct 03, 2020 | Category :coding | Tags : algorithm backtracking data-structure easy leetcode

Binary Watch - Immutable - Array - Easy - LeetCode

Binary Watch - Immutable - Array - Easy - LeetCode

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.


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

public class Solution {
    public IList<string> ReadBinaryWatch(int num) {
        var res = new List<string>();
        for(int i=0;i<12;i++){
            for(int j=0;j<60;j++){
                if(NumberOfSetBits(i)+NumberOfSetBits(j)==num){
                    res.Add(i+":"+((j<10)?"0":"")+j);
                }
            }
        }
        
        return res;
    }
    
    private int CountBits(int num){
        int count = 0;
        while (num != 0)
        {
            count++;
            num &= num - 1;
        }
        return count;
    }
    
    private int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }
}

Time Complexity: O(1) // since minutes and hours are constant.

Space Complexity: O(1)

Contributed By: Sumit Chourasia
Rotate Image - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Majority Element II - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Teemo Attacking - Array - Medium - LeetCode