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


1000000 (1)

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.

How fast is your code?

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.

9 Comments (+add yours?)

  1. max
    Jul 25, 2014 @ 18:33:04

    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]

    Reply

    • 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

      -(-) = + :)

      Reply

      • max
        Jul 26, 2014 @ 11:54:23

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

  2. marameo00
    Jul 25, 2014 @ 23:47:59

    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)?

    Reply

  3. marameo00
    Jul 25, 2014 @ 23:54:31

    Reply

  4. marek
    Jul 26, 2014 @ 05:38:44

    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.

    Reply

  5. marek
    Jul 26, 2014 @ 05:47:39

    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.

    Reply

  6. Michael van Niekerk
    Jul 28, 2014 @ 06:32:06

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 547 other followers

%d bloggers like this: