Leetcode 0401 Binary Watch

Problem statement

https://leetcode.com/problems/binary-watch/

Solution

The easiest way is to iterate over all possible times, count number of non-zero bits and return all possible candidates.

Complexity

Time and space complexity is O(H * M).

Code

class Solution:
    def readBinaryWatch(self, num):
        ans = []
        for h in range(12):
            for m in range(60):
                if (bin(h) + bin(m)).count("1") == num:
                    ans += [str(h) + ":" + "0"*(2 - len(str(m))) + str(m)]
        return ans

Remark

If we have more general case, then we can use backtracking: we need generate binary strings and then transform them to decimal, or do bit manipulations: dfs(n, hours, mins, idx). Complexity is similar, but a bit smaller, something like $O(C_{10}^n)$.