Sort 24 Discussions, By:
Please Login in order to post a comment
The original Project Euler problem is very clear, however this problem statement makes no sense whatsoever. Something might have gotten lost in translation. Could a moderator please review?
where is the number 1?
1 * 1 = 1, 1 * 2 = 2, ..., 1 * 8 = 8. So basically pandigital.
Exactly ... The problem statement should specify that we're only looking for numbers > 1.
Its written there 1 < M in the constraints part.
My attempt at an alternate explanation to the problem statement:
Find all numbers between 2 and N whose concatenated product gives a pandigital.
A 1-K pandigital is defined in this problem as a K-digit number that only contains the numbers 1,2,3,...,K. So if K=4 then the number 1423 would be a pandigital since all the numbers from 1,2,3,4 is present and it's a 4-digit number. The number 12334 on the other hand isn't counted as a pandigital number since it's not a 4-digit number as required. Similarly, the number 1023 isn't 1-4 pandigital since all the numbers between 1,..,4 isn't included in the number (namely 4).
To find the concatenated product of the number, you need to multiply it with 1,2... until the length of the concatenated product is equal to or above K. I'll use K=8 as in the example. If we want to find the concatenated product of 2, then we'd first multiply it with 1 and then add it to our concatenated product (which I'll call p):
1*2 = 2
p <- 2
p = 2
Since p isn't a 8-digit number, we'll have to keep multiplying our number.
2*2 = 4
p <- 4
p = 24
We'll continue this procedure until p is an 8-digit number.
3*2 = 6
p <- 6
p = 246
4*2 = 8
p <- 8
p = 2468
5*2 = 10
p <- 10
p = 246810
6*2 = 12
p <- 12
p = 24681012
Now that p is a 8-digit number we can check if it's pandigital. Since all number from 1 to 8 doesn't appear in p, then we know that the number 2 doesn't meet the criteria and shouldn't be printed. Do this procedure from 2 to N as previously mentioned and print only those number whose concatenated product is pandigital.
I hope this helped. Good luck.
At first, I was spending a lot of time thinking of what possible sets (1, 2, ..., n) would work in order to optimize. Then I discovered that trying all concatenated products N x (1, 2, ..., i) for 1 <= i <= 9, 1 <= N < 10,000 was still plenty fast.
The problem does not state that something like 9x9, 9x8, 9x7, 9x6 giving 81726354 would be illegal, but it can (only) be inferred from the sample output.:) :(