Friday, April 15, 2011

Project Euler - Problem 9 - C#

/*
 A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,

 a^2 + b^2 = c^2
 For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

 There exists exactly one Pythagorean triplet for which a + b + c = 1000.
 Find the product abc.
 */
static int Problem9()
{
 /* HLD:
  * a + b + c = 1000 ==>  c = 1000 - a - b
  * foreach {a, b} in {{1,1}, {1,2} ... {2,2} ... {499,1} ... {499,499}}
  * predicate of pass: a^2 + b^2 = c^2
  */

 var solution_found = false;
 int a = 0, b = 0;
 int c = 1000;

 for (b = 1; b < 499; b++)
 {
  c = 1000;

  for (a = b; a <= c; a++)
  {
   c = 1000 - a - b;

   if ((a * a + b * b) == (c * c))
   {
    solution_found = true;
    break;
   }
  }

  if (solution_found)
  {
   break;
  }
 }

 return a * b * c;

 // Problem9: 31875000
}

No comments:

Post a Comment