In some algorithm design problems, the problem can be expressed as a format like this:
Given a system which can be described as a function $f$. Find all the possible $x\in X$ such that$f(x)=y$, where y is given.
Ideally, we should analyze the property of $x$ and try to narrow down the range of $x$ so we can search for the solution more efficiently. But in some cases, it is not easy to come up with a good reasoning to eliminate the possible domain of $x$ or search in a fancy way. If that is the case, an exaustive method aided with a reasonable stopping criteria might work better than expected.
In this article, I will discuss solutions for two problems from Leetcodes' problem set and demonstrate why exaustive methods work.
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, if the lights on the watch is (1 for on and 0 for off):
Row 1: 0-0-1-1
Row 2: 0-1-1-0-0-1
The reading is 3:25. As the binary number (0011) is 3 and (011001) is 25.Give: a non-negative integer n which represents the number of LEDs that are currently on.
Ask: return all possible times the watch could represent.
Answer: If we think in the normal "forward" direction, we should consider how many of lights are on the first row ($x_1$) and how many of them are on the second row ($x_2$); then we have to solve for what possible numbers can be represented by $x_1$ and $x_2$. It is possible to do it this way, but it is very heavy to digest in minds.
Since the number of hours and minutes are limited: 0 to 11 for hours and 0 to 59 for minutes, a simpler approach could be to just list all the possible hour/minute numbers and check whether the number of 1s in the binary representation match the total number of LED or not.
Below is my solution in python code. You can see 3:25 is among the solutions.
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
rst = []
for hr in range(12):
for mn in range(60):
if bin(hr).count('1') + bin(mn).count('1') == num:
tstr = str(hr) + ":" + "{:02d}".format(mn)
rst.append(tstr)
return rst
sln = Solution()
print(sln.readBinaryWatch(5))
Given a function f(x, y) and a value z, return all positive integer pairs x and y such that f(x,y) == z.
The function is constantly increasing, i.e.:
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
The function interface is defined like this:
interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};
Answer: The information about the function itself is rather limited: increasing function and we are looking for integer solution only. Therefore, we have to do a search within the integer numbers.
At this point, binary search map pop up as it is able to speed up the search. Another question is what the boundary of the searching space should be. Obviously we have to use the property of increasing function.
Below is my solution by exhausting possible solutions in the possible domain of x and y (integers smaller than 'xmax').
class Solution(object):
def findSolution(self, customfunction, z):
"""
:type num: int
:type z: int
:rtype: List[List[int]]
"""
xmax = 1000
sln = []
# Double loop to go from small numbers to large ones:
for x in range(1, xmax+1):
for y in range(1, xmax+1):
# Find a solution, record it:
if customfunction(x, y) == z:
sln.append([x, y])
# If f(x,y) > z but y == 1, then there is no more solutions (as
# any x,y would produce a larger number).
elif customfunction(x, y) > z and y==1:
return sln
# Otherwise, we should stop increasing y; instead try to
# increase x.
elif customfunction(x,y) > z:
break
return sln
# For testing purpose, let's assume the customfunction is summation.
def my_sum_of_two(x,y):
return x + y
sln = Solution()
print(sln.findSolution(my_sum_of_two, 5))
The key in the above solution is the stopping criteria. We have to be very careful with the condition of breaking the loop for y and then breaking the whole search loop.
Even without fancy binary search, this solution is faster than 80% of the submissions.
In this article, we discussed the idea of exhaustive methods to solve unknowns in complex models which are hard to decode otherwise. Although it is a direct method, sometimes it is not trivial to set the stopping criteria in a correct and efficient way.