Formatted question description: https://leetcode.ca/all/401.html

401. Binary Watch

Level

Easy

Description

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.

Image text

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

Solution

Loop over all possible times. For each possible time, calculate the number of LEDs that are on, and if the number equals the given num, add the time to the result list. Finally, return the result list.

  • class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> timeList = new ArrayList<String>();
            for (int i = 0; i < 12; i++) {
                int minuteOnes = onesCount(i);
                if (minuteOnes > num)
                    continue;
                for (int j = 0; j < 60; j++) {
                    int secondOnes = onesCount(j);
                    if (minuteOnes + secondOnes == num) {
                        String time = toTime(i, j);
                        timeList.add(time);
                    }
                }
            }
            return timeList;
        }
    
        public int onesCount(int num) {
            int ones = 0;
            int remain = num;
            while (remain > 0) {
                ones += remain % 2;
                remain /= 2;
            }
            return ones;
        }
    
        public String toTime(int hour, int minute) {
            return hour + ":" + getTwo(minute);
        }
    
        public String getTwo(int num) {
            String str = String.valueOf(num);
            if (num < 10)
                str = "0" + str;
            return str;
        }
    }
    
  • Todo
    
  • class Solution(object):
      def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        ans = []
        for i in range(0, 12):
          for j in range(0, 60):
            if (bin(i) + bin(j)).count("1") == num:
              ans.append("%d:%02d" % (i, j))
        return ans
    
    

All Problems

All Solutions