Project Euler Problem 75 Solution

Project Euler Problem 75 Statement

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

• 12 cm: (3,4,5)
• 24 cm: (6,8,10)
• 30 cm: (5,12,13)
• 36 cm: (9,12,15)
• 40 cm: (8,15,17)
• 48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

• 120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that $L$ is the length of the wire, for how many values of $L \le 1\,500\,000$ can exactly one integer sided right angle triangle be formed?

Solution

HackerRank Project Euler Problem 75 overview:

For a given upper bound $N$, how many integer perimeters (where a perimeter $L\le N$) can form exactly one right-angled triangle with integer side lengths $(a, b, c)$ (with $a^2 + b^2 = c^2$) that sums to that particular perimeter $L = a + b + c$.

Solution Summary

This script precomputes, for every perimeter up to 5,000,000, whether that perimeter can be formed by exactly one right-angled triangle with integer sides. (In other words, it "flags" those perimeters that yield a singular solution.) It then uses a prefix sum array so that each query (given a number $N$) can be answered in $O(1)$ time.

Solution Details

1. Setting Up the Limit and the Count Array

import math, bisect, itertools
L = 5 * 10**6
f = [0]*L

• L = 5 * 10**6
  This sets the maximum perimeter limit (in this code, the "perimeter" means the one computed by our formula – see below) to 5 million. (Depending on the formulation, you might think of the number as an upper bound on the perimeter that you wish to consider.)
• f = [0]*L
  This creates a list (f[]) of length L where each index represents a candidate perimeter. The final goal is for f[p] (where p is a perimeter) to count the number of distinct right triangles that can be formed with that perimeter. We initialize it with zeros.

2. Generating Primitive Pythagorean Triples Using a Change of Variables

The standard Euclid's formula to generate a primitive Pythagorean triple is $$a = m^2 - n^2,\quad b = 2mn,\quad c = m^2 + n^2,$$ and the perimeter $$P = a+b+c = 2m(m+n),$$ where \(m\) and \(n\) are positive integers with:

• \(m > n\),
• \(\gcd(m, n)=1\),
• \(m-n\) is odd.

This script uses a transformation that lets it iterate over pairs of odd numbers instead. Here's how:

for i,j in itertools.combinations(range(1, math.isqrt(L), 2), 2):
    if j>i and math.gcd(j, i)==1:
        s = j*(j + i)
        for i in range(s, L, s):f[i]+=1

What is happening here?

• Iteration over Odd Numbers:
  The loop itertools.combinations(range(1, math.isqrt(L), 2), 2) iterates over all pairs \((i, j)\) of odd numbers from 1 up to math.isqrt(L) (the integer square root of \(L\)). By choosing only odd numbers, we guarantee that the sums and differences coming later are even – so that when we define new parameters, we get integers.
• Recovering \(m\) and \(n\):
  With the substitution $$m = \frac{i+j}{2} \quad \text{and} \quad n = \frac{j-i}{2},$$ notice that:
  • \(m > n > 0\) (since \(j > i\)), and
  • The condition \(\gcd(j, i) = 1\) ensures that \(\gcd(m, n)=1\) (this is equivalent to the usual coprimality condition in Euclid's parameterization).
• Primitive Perimeter Formula:
  With these definitions, the standard perimeter becomes $$P = 2m(m+n).$$ Now observe that $$2m(m+n) = 2\frac{i+j}{2} \cdot \frac{i+2j}{2} = j \cdot (i+j)$$ (after rearranging the terms properly). In the code, the variable s is set as: s = j * (j + i) which turns out to be exactly the perimeter \(P\) of the primitive triple.
• Marking All Multiples (Scaling Up):
  Every primitive triple can be scaled by an integer factor \(k \ge 1\) to yield a non-primitive (but still valid) triple with perimeter \(kP\). So the inner loop: for i in range(s, L, s): f[i] += 1 runs over all multiples of the primitive perimeter s up to the limit L and increments the count f[i]. In effect, after processing all pairs, f[p] is the total number of distinct right triangle representations (coming from any primitive triple and its multiples) for the perimeter p.

3. Filtering Singular Perimeters

After the double loop finishes, we want to know which perimeters can form exactly one right triangle. That is, we are interested in perimeters \(p\) such that f[p] == 1.

f = [i for i in range(L) if f[i]==1]

This list comprehension builds a new sorted list, storing only those perimeter values i (from 0 up to L-1) for which there is exactly one right triangle. These are the singular integer right triangles perimeters.

4. Answering the Queries Fast with Binary Search

Finally, the script processes multiple queries. For each query, it needs to count how many singular perimeters are less than or equal to a given integer.

for _ in range(int(input())):
    print(bisect.bisect_right(f, int(input())))

Input Handling:
The first input is the number of queries. For each query, the script reads an integer value (say, \(N\)).

Using bisect_right:
The list f is already sorted (since it was constructed in increasing order). The function bisect.bisect_right(f, N) returns the insertion index of \(N\) in f – which is exactly the number of elements in f[] that are \(\leq N\). In other words, it counts how many singular perimeters do not exceed \(N\).

Printing the Result:
The result is printed for each query.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 75

HackerRank Project Euler 75: Given that $L$ is the length of the wire, for how many values of $L≤ N$ where (12 ≤ N ≤ 10^6) can exactly one integer sided right angle triangle be formed?