Welcome to Subscribe On Youtube

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.

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.

• Java
• Python
• C++
• Go
• TypeScript
• RenderScript

• 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;
      }
  }
  

• class Solution:
      def readBinaryWatch(self, turnedOn: int) -> List[str]:
          return [
              '{:d}:{:02d}'.format(i, j)
              for i in range(12)
              for j in range(60)
              if (bin(i) + bin(j)).count('1') == turnedOn
          ]
  
  ############
  
  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
  
  

• class Solution {
  public:
      vector<string> readBinaryWatch(int turnedOn) {
          vector<string> ans;
          for (int i = 0; i < 12; ++i) {
              for (int j = 0; j < 60; ++j) {
                  if (__builtin_popcount(i) + __builtin_popcount(j) == turnedOn) {
                      ans.push_back(to_string(i) + ":" + (j < 10 ? "0" : "") + to_string(j));
                  }
              }
          }
          return ans;
      }
  };
  

• func readBinaryWatch(turnedOn int) []string {
  	var ans []string
  	for i := 0; i < 12; i++ {
  		for j := 0; j < 60; j++ {
  			if bits.OnesCount(uint(i))+bits.OnesCount(uint(j)) == turnedOn {
  				ans = append(ans, fmt.Sprintf("%d:%02d", i, j))
  			}
  		}
  	}
  	return ans
  }
  

• function readBinaryWatch(turnedOn: number): string[] {
      if (turnedOn === 0) {
          return ['0:00'];
      }
      const n = 10;
      const res = [];
      const bitArr = new Array(10).fill(false);
      const createTime = () => {
          return [
              bitArr.slice(0, 4).reduce((p, v) => (p << 1) | Number(v), 0),
              bitArr.slice(4).reduce((p, v) => (p << 1) | Number(v), 0),
          ];
      };
      const helper = (i: number, count: number) => {
          if (i + count > n || count === 0) {
              return;
          }
          bitArr[i] = true;
          if (count === 1) {
              const [h, m] = createTime();
              if (h < 12 && m < 60) {
                  res.push(`${h}:${m < 10 ? '0' + m : m}`);
              }
          }
          helper(i + 1, count - 1);
          bitArr[i] = false;
          helper(i + 1, count);
      };
      helper(0, turnedOn);
      return res;
  }
  
  

• impl Solution {
      fn create_time(bit_arr: &[bool; 10]) -> (i32, i32) {
          let mut h = 0;
          let mut m = 0;
          for i in 0..4 {
              h <<= 1;
              h |= if bit_arr[i] { 1 } else { 0 };
          }
          for i in 4..10 {
              m <<= 1;
              m |= if bit_arr[i] { 1 } else { 0 };
          }
  
          (h, m)
      }
  
      fn helper(res: &mut Vec<String>, bit_arr: &mut [bool; 10], i: usize, count: usize) {
          if i + count > 10 || count == 0 {
              return;
          }
          bit_arr[i] = true;
          if count == 1 {
              let (h, m) = Self::create_time(bit_arr);
              if h < 12 && m < 60 {
                  if m < 10 {
                      res.push(format!("{}:0{}", h, m));
                  } else {
                      res.push(format!("{}:{}", h, m));
                  }
              }
          }
          Self::helper(res, bit_arr, i + 1, count - 1);
          bit_arr[i] = false;
          Self::helper(res, bit_arr, i + 1, count);
      }
  
      pub fn read_binary_watch(turned_on: i32) -> Vec<String> {
          if turned_on == 0 {
              return vec![String::from("0:00")];
          }
          let mut res = vec![];
          let mut bit_arr = [false; 10];
          Self::helper(&mut res, &mut bit_arr, 0, turned_on as usize);
          res
      }
  }
  
  

All Problems

All Solutions