3
\$\begingroup\$

Write a function maxPythagTriple that accepts an integer n and returns the maximum product of three numbers that are both a Pythagorean triplet and sum to the integer n. If no such pythagorean triplet exists, return -1.

i.e. maxPythagTriple(4) == -1 i.e. maxPythagTriple(12) == 60 {3,4,5} --> 3+4+5 = 12 --> 3^2+4^2= 5^2 --> 3*4*5 = 60

Below is my solution the preceeding challenge. I have been told there is a better solution. Any help would be much appreciated!

package challenges;

public class MathChallenges {

    private static boolean isValidTriple(int i, int j, int k) {
        return k > 0 && i != j && j != k && i > j && j > k;
    }

    private static boolean isPythagTriple(int i, int j, int k) {
        return (i*i + j*j) == k*k;
    }

    public static int maxPythagTriple(int n) {
        for (int i = n-1; i >= 1; i--) {
            for (int j = i-1; j >= 1; j--) {
                int k = n - (i + j);
                if (isValidTriple(i, j, k) && isPythagTriple(k, j, i)) {
                    return i * j * k;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println("maxPythagTriple(4) = " + maxPythagTriple(4));
        System.out.println("maxPythagTriple(12) = " + maxPythagTriple(12));
    }

}
\$\endgroup\$
2
\$\begingroup\$

The code returns the first product, not the maximum product. For example, it returns 6240 instead of 7500 on input 60:

(60)  10² + 24² = 26² ; 10 * 24 * 26 = 6240
(60)  15² + 20² = 25² ; 15 * 20 * 25 = 7500

This is easy to fix: loop and take the maximum.

I have been told there is a better solution.

There are solutions that take fewer steps. One could attempt to improve the current solution by shrinking the possible ranges. Given:

\$c^2 = a^2 + b^2 ; sum = a + b + c\$

Neither a nor b can be larger than c. This also means that neither a nor b can be larger than half the sum.

For c: it can't be smaller than any other term, and it must be at least one-third of the sum.

  // the "sum - 1" accounts for a being at least 1
  for ( int b = (sum - 1) / 2; b >= 1; b-- ) {
    for ( int c = Math.max(b, sum - 2*b); c < sum-b-1; c++ ) {
      int a = n - b - c;
      if ( a*a + b*b == c*c ) {
        // found a triple
      }
    }
  }

This is a little better, but it's still inefficient. If you're feeling brave, there is a formula to generate all Pythagorean triples.

Euclid's Formula

Briefly, Euclid's formula involves two integers, \$m > n > 0\$, that generate Pythagorean triples:

\$a = m^2 - n^2 ; b = 2mn ; c = m^2 + n^2\$

(This doesn't generate all triples; we'll get to that in a minute.)

The sum of a, b, c becomes:

\$sum = m^2 - n^2 + 2mn + m^2 + n^2 = (m - n)(m + n) + (m + n)^2 = 2m(m + n)\$

Because sum, m, and n are integers, this means that both m and (m+n) divide sum.

For minimal n = 1, m is maximally \$\sqrt{sum \over 2}\$, so that's a good upper bound to start with. And given sum and m, we have \$n = {sum \over {2m}} - m\$

/* sum = 2m(m+n) ; m > n > 0 */
public static int maxPythagTriple_Euclid(int sum) {
  // sum must be even; smallest triple has sum 12
  if ( sum % 2 != 0 || sum < 12 ) return -1;
  final int sumd2 = sum / 2; // divisible by 2
  for ( int m = (int) Math.sqrt(sumd2); m > sumd2 / m - m; m-- ) {
    if ( sum % m != 0 ) continue; // must be a divisor
    final int n = sumd2 / m - m;
    if ( n <= 0 ) continue; // rule out pathologicals
    if ( sum % (m+n) != 0 ) continue; // must be a divisor
    final int msq = m*m, nsq = n*n;
    final int a = msq - nsq, b = 2*m*n, c = msq + nsq;
    assert a * a + b * b == c * c;
    return a * b * c;
  }
  return -1;
}

// Alternative implementation, pulling n into the for-loop
public static int maxPythagTriple_Euclid(int sum) {
  if ( sum % 2 != 0 || sum < 12 ) return -1;
  final int sumd2 = sum / 2; // divisible by 2
  for ( int m = (int) Math.sqrt(sumd2), n = sumd2 / m - m;
            m > n;
            m--, n = sumd2 / m - m ) {
    if ( n <= 0 || sum % m != 0 || sum % (m+n) != 0 ) {
      continue;
    }
    final int msq = m*m, nsq = n*n;
    final int a = msq - nsq, b = 2*m*n, c = msq + nsq;
    assert a * a + b * b == c * c;
    return a * b * c;
  }
  return -1;
}

We can return at our first hit because we maximize m; the product will be largest when the terms are closest, which is the case for minimal n (and thus maximal m).

To quote myself:

This doesn't generate all triples; we'll get to that in a minute.

Euclid's formula doesn't generate all triples, but it does generate at least all primitive triples.

An important property of Pythagorean triples is that, if \$(a,b,c)\$ is a triple, then so is \$(k*a, k*b, k*c)\$, for any integer k. Such a k is necessarily a divisor of the sum of a, b, c.

public static int maxPythagTriple_Euclid(int sum) {
  int max = -1;
  for ( int k = 1; k < sum / 2 && sum / k >= 12; k++ ) {
    if ( sum % k != 0 ) continue;

    // multiply by k^3
    int prod = maxPythagTriple_Euclid_primitive(sum / k) * (k * k * k);
    if ( prod > max ) {
      max = prod;
    }
  }
  return max;
}

Precomputing the divisors of sum may save some more steps, but I haven't looked into that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.