401.Binary Watch

Tags: [binary], [recursion], [choose_or_not]

Link: https://leetcode.com/problems/binary-watch/?tab=Description

A binary watch has 4 LEDs on the top which represent thehours(0-11), and the 6 LEDs on the bottom represent theminutes(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: binary, recursion, choose_or_not

class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        if not num:
            return ['0:00']

        result = []
        num_of_top_lights = 0
        while num_of_top_lights <= 4 and num_of_top_lights <= num:
            result += self.possible_time(num_of_top_lights, num - num_of_top_lights)
            num_of_top_lights += 1

        return result

    def possible_time(self, num_of_top_lights, num_of_bottom_lights):
        possible_hours = self.get_all_possible_nums(4, num_of_top_lights)
        possible_minutes = self.get_all_possible_nums(6, num_of_bottom_lights)

        result = []
        for h in possible_hours:
            for m in possible_minutes:
                if m < 10:
                    m_s = '0{}'.format(m)
                else:
                    m_s = str(m)
                result.append('{}:{}'.format(h, m_s))

        return result

    def get_all_possible_nums(self, num_of_digits, num_of_ones):
        result = []
        buff = []
        self.get_all_possible_nums_helper(num_of_digits, num_of_ones, result, buff)
        return result

    def get_all_possible_nums_helper(self, num_of_digits, num_of_ones, result, buff):
        # base case
        if len(buff) == num_of_digits:
            if num_of_ones == 0:
                num = self.get_num_by_binary_representation(buff)
                if num_of_digits == 4 and num <= 11:
                    result.append(num)
                elif num_of_digits == 6 and num <= 59:
                    result.append(num)
            return

        buff.append(0)
        self.get_all_possible_nums_helper(num_of_digits, num_of_ones, result, buff)
        buff.pop()

        buff.append(1)
        self.get_all_possible_nums_helper(num_of_digits, num_of_ones - 1, result, buff)
        buff.pop()

    def get_num_by_binary_representation(self, binary_arr):
        if not binary_arr:
            return 0

        result = 0
        counter = 0
        for i in xrange(len(binary_arr) - 1, -1, -1):
            digit = binary_arr[i]
            result += digit * pow(2, counter)
            counter += 1

        return result

Revelation:

• Subdivide the problem to each small problem.

Note:

• Time complexity = O(1), explanation: T = O(4 * ((choose k from 4) + (choose n - k from 6) + (choose k from 4) * (choose n - k from 6))), k <= 4, because O(choose k from 4) = 4! / k! * (4 - k)! = O(1), O(choose n - k from 6) = 6! / (n - k)! * (6 - n + k)! = O(1).
• Do not forget to check the generated hour <= 11 and generated minute <= 59, based on the requirement.