Interview question: find solution to x! + y! + z! = x * y * z

Interview question: find solution to x! + y! + z! = x * y * z

  • Comments 7

I stumbled on hmlee's algorithm chart quite by chance.  A lot of good questions in there.

Question 53 caught my eye as a mathematician.

Q53: Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = ABC (where ABS is a three digit numbers, not A * B * C). Find A, B, and C that satisfies this equation.

Interesting. But I'd like to modify the question a little.

Q53': Say you have three integers between 0 - 9. You have the equation: A! + B! + C! = A * B * C.
Find A, B, and C that satisfies this equation.

Astute readers will notice that A, B, and C are interchangeable.  Nonetheless there is a unique solution (modulo swapping A, B, and C.)

I'm much less interested in the answer to this question (I know the answer) than I am in the quality of the program used to find the answer.  (I tried finding the answer by hunt-and-peck, then gave up and wrote a program - I find the program to be more interesting than the answer.)  Try to find the solution as efficiently as possible (without cheating.)

I'll post my program later.

If you see a fact, try to see it as intuitively as possible.

I suspect that the following even more general problem has the same unique solution, which would be very interesting indeed.  This is the kind of thing where programs fail, and the mathematical mind becomes necessary again:

Q53'': Say you have three integers that are >= 0. You have the equation: A! + B! + C! = A * B * C.
Find A, B, and C that satisfies this equation.

Leave a Comment
  • Please add 6 and 6 and type the answer here:
  • Post
  • we can assume that a>=b>=c (if not rearrange them)

    for a>=5 there are not solutions as 6!=720 > a*a*a, hence the program below:

           static void Main(string[] args)

           {

               int[] F = new int[6];

               for (int a = 0; a < 6; a++)

               {

                   var fa = F[a] = a==0 ? 1 : F[a-1]*a;

                   for (int b = 0; b <= a; b++)

                   {

                       var fb = F[b];

                       for (int c = 0; c <= b; c++)

                       {

                           var fc = F[c];

                           if (fa + fb + fc == a*b*c)

                               Console.WriteLine("{0} {1} {2}", a, b, c);

                       }

                   }

               }

               Console.ReadLine();

           }

    I hope you find this efficient :)

  • You nailed it.  I want to expound a little more on this in a future post.

  • My son just noticed that I should have started all loops from 1 not from 0 as a*b*c would be zero if a or b or c is zero.

    It saves a bit :)

    The other optimisations would be:

    1/ keep a*b where fb is calculated

    2/ notice that except 1! all factorials are even, so all a,b,c cannot be all odd at the same time

    But somehow, I have a feeling that all those optimisations have not a lot of sense, bearing in mind that the whole algorithm takes couple of microseconds anyway :)

  • Follow-up here:

    http://blogs.msdn.com/matthew_van_eerde/archive/2008/08/08/solution-x-y-z-x-y-z.aspx

  • NOT (x+y) = not X + NOT y ....

    why is this ?

  • > NOT (x+y) = not X + NOT y

    Sorry, I don't follow.  Is this a symbolic logic question: "~(x v y) = ~x v ~y"?  If so, that's false; De Morgan's law requires flipping v to ^ and vice versa: "~(x v y) = ~x ^ ~y".

    If it's just a general philosophical observation, then, you go, girl.

  • To be more explicit (using ~ to denote logical negation, to avoid confusion with the factorial symbol:)

    0 0 1 1 : x

    0 1 0 1 : y

    1 1 0 0 : ~x

    1 0 1 0 : ~y

    0 1 1 1 : x v y

    1 0 0 0 : ~(x v y)

    1 1 1 0 : ~x v ~y

    1 0 0 0 : ~x ^ ~y

    Note that ~(x v y) is not always equal to ~x v ~y, but is always equal to ~x ^ ~y.

Page 1 of 1 (7 items)