Two Digits and a Number – Part 1: The Mistake
As an old wise man used to say: “for every complicated
problem, there is always an easy solution, albeit a wrong one”. Indeed.
D2 = 4
N = 16
One would be tempted to write a recursive solution like this (sketch, pseudo-code):
FindMinMultiple(d1, d2, n, 10 * generatedNumber + Min(d1,d2))
FindMinMultiple(d1, d2, n, 10 * generatedNumber + Max(d1,d2))
}
What’s wrong with this solution, and what would the right solution be? Answers in the next post. By the way, you should try to find a solution for
D1 = 3
D2 = 7
N = 987654321
Ok, an example with real numbers will make this easier to
visualize.
D1 = 1D2 = 4
N = 16
What’s the smallest number composed of only “1”s and “4”s
that is a multiple of 16? The answer is 144. Also, assume that there is always
a solution.
One would be tempted to write a recursive solution like this (sketch, pseudo-code):
FindMinMultiple(int d1, int d2, int n, int generatedNumber){
If(generatedNumber%n
== 0) è
found!FindMinMultiple(d1, d2, n, 10 * generatedNumber + Min(d1,d2))
FindMinMultiple(d1, d2, n, 10 * generatedNumber + Max(d1,d2))
}
What’s wrong with this solution, and what would the right solution be? Answers in the next post. By the way, you should try to find a solution for
D1 = 3
D2 = 7
N = 987654321
With Love,
Marcelo
Thanks Marcelo for an interesting article!
ReplyDeleteAs for problems with provided solution:
- it's not going to terminate if there are no multiples. Easy test case would be D1 = 1, D2 = 3, N = 2. Since all numbers created from 1s and 3s will be odd, there will never be a multiple of 2.
- it will always try to find a multiple that consists of MIN(D1,D2) before checking the other branch.
Both of these limitations can be avoided by using a BFS instead of using DFS (as in provided implementation). A very simple implementation would look as follows:
val MAX_DEPTH: Int = ;
def findMinMultiple(d1: Int, d2: Int, n: Int): Int = {
lazy val minMultiples = d1.min(d2) #:: d1.max(d2) #:: (minMultiples.flatMap { m => Stream.cons(m * 10 + d1.min(d2), Stream.cons(m * 10 + d1.max(d2), Stream.empty)) } ).filter(m => m % n == 0).take(MAX_DEPTH)
minMultiples.head
}
Note: this solution can be easily improved to use BigInt instead of Int to be able to tackle bigger numbers, but it's suffices to show the solution.
The solution uses BFS and as such is not going to be stuck on the MIN(D1,D2) branch and it also has a MAX_DEPTH limit to stop if we can't find a multiple after exploring MAX_DEPTH number of solutions from solution space.
Thanks again Marcelo!
PS.: practically the recursive function provided in your post won't run forever, as it will very quickly overflow the stack and stop :)
ReplyDeleteTaras, as always, you're flawless!!! :) I also love your elegant coding style! Now find the solution for:
ReplyDeleteD1 = 3
D2 = 7
N = 987654321
Cheers my friend!!!