## Weekend Programming Challenge – Week #62 – One million :)

One million is good round number 🙂 Your task for the weekend challenge is to write code which check if you can find two numbers X and Y which product makes exactly 1 000 000, the catch is that none of these numbers should contain 0 inside it.

## The rules:

You can code the solution in any programming language during the weekend and have to submit it to info@olimex.com latest on Sunday July 27th.

On Monday we will upload the solutions on GitHub https://github.com/OLIMEX/WPC

You can play with your real name or with nick if you want to be anonymous, we will not disclosure your personal info if you do not want to.

1. 1,000,000 = 10^6 = 5^6 * 2^6
All possible pair of positive integer factors are (5^m * 2^n, 5^(6-m) * 2^(6-n) ) with n,m = 0..6
BUT if you put a five with a two in a factor you get a multiple of 10, then you get a zero. Fives and twos must remain separate.
So the only remaining combination should be (5^6, 2^6) = (15625, 64)
Am I missing anything?
If you know that X * Y = 1,000,000 you only need to check if neither one is divisible by 10.
result = ! ( (X % 10 == 0) || (Y % 10 == 0) )
or, since there’s only 1 solution
result = (X == 64) || (Y == 64) [once we know that X*Y=1,000,000]

• Edoardo Codeglia
Jul 26, 2014 @ 00:40:11

Also it’s worth to remember that there are actually four solutions 🙂

15625*64
64*15625
-64*-15625
-15625*-64

-(-) = + 🙂

• That’s why I wrote “positive integer factors” and “combination” (instead of permutation). Under those restrictions, the solution should be unique.

2. So now anybody submit his code. But this is sure the best solution. I thought there’s a solution like yours but I’m not able to find.
Is it possible to generalize the solution for generic X*Y=Z (all integers value) so that X nor Y cantains digit 0 (or even better digit d)?

3. Note 2^10 is 1024 and has a 0, so not being divisible by 10 doesn’t guarantee there isn’t a zero in the solution. That is if you’re writing a generalized solution which factors any number.

4. 7000000 makes an interesting test case, where all the 2 factors are grouped (64), all the 5 factors are grouped (15625) and the 7 factor needs to be assigned to (64).

My brute-force approach would be to factor Z, and create all possible combinations (non-duplicate) of the factors and see which ones have and don’t have 0’s.

• It wont work for 3e10 = 3 * 2^10 * 5^10 (3072 * whatever).

5. I don’t know how to submit – but https://github.com/mvniekerk/OlimexWeekend94 here’s my code.
Followed the brute force method mostly.