Right-angle frames from rods

Scenario

A framing workshop sells wooden rods, cut to exact lengths in whole millimetres. A carpenter's rule says that three rods form a right-angle frame when the squares of the two shorter lengths add up to the square of the longest.

The shop's screen shows customers how many different ways they can pick three rods from the shelf to build such a frame. You are asked to write that count. Two rods of the same length are still two different rods.

Your task

Write count_right_triples(rods).

rods[i] is the length of the i-th rod in millimetres. The list is not sorted, and lengths may repeat.
A triple is three different positions in the list. Call their lengths a, b and c, with c the longest.
The triple forms a frame when a * a + b * b == c * c.
Return the number of triples that form a frame. Return 0 if there is none.

Examples

Example 1 (traced)#

text2 lines

Input:  rods = [12, 5, 3, 13, 5, 4]
Output: 4

Sorted, the rods are [3, 4, 5, 5, 12, 13]. Fix each rod k from the third on as the longest one, c. Put lo at the shortest rod and hi at the rod before c, and compare a² + b² with c². When they match, count every rod of length a with every rod of length b, and skip both runs.

c (at k)	lo	hi	a, b	a² + b²	c²	Action	count after
5 (k = 2)	0	1	3, 4	25	25	match: 1 rod of 3, 1 rod of 4, so add 1	1
5 (k = 3)	0	2	3, 5	34	25	too much: hi becomes 1	1
5 (k = 3)	0	1	3, 4	25	25	match: add 1	2
12 (k = 4)	0	3	3, 5	34	144	too little: lo becomes 1	2
12 (k = 4)	1	3	4, 5	41	144	too little: lo becomes 2	2
12 (k = 4)	2	3	5, 5	50	144	too little: lo becomes 3, the walk ends	2
13 (k = 5)	0	4	3, 12	153	169	too little: lo becomes 1	2
13 (k = 5)	1	4	4, 12	160	169	too little: lo becomes 2	2
13 (k = 5)	2	4	5, 12	169	169	match: 2 rods of 5, 1 rod of 12, so add 2	4

The four frames are the rods 3, 4, 5 with either rod of length 5, and the rods 5, 12, 13 with either rod of length 5.

Example 2#

text2 lines

Input:  rods = [6, 8, 10, 10, 10]
Output: 3

The rods 6, 8, 10 form a frame. Any of the three rods of length 10 can be the longest, so there are three frames.

Example 3#

text2 lines

Input:  rods = [5, 6, 7, 8, 9]
Output: 0

No two rods have squares that add up to the square of a third.

Constraints

1 ≤ rods.length ≤ 3,000 (rods on the shelf)
1 ≤ rods[i] ≤ 10,000 (lengths in millimetres)

What does n ≤ 3,000 tell you?

Checking every triple costs about n × n × n ÷ 6 triples. At n = 3,000 that is about 4.5 × 10^9, roughly 45 seconds at 10^8 operations a second. Fixing the longest rod and walking two pointers over the others costs about n × n ÷ 2 steps, 4.5 million.

A square can reach 10^8, and the sum of two squares 2 × 10^8, which fits in 32 bits. The count can reach about 10^9 when 1,000 rods share each of three lengths, so the answer is a 64-bit integer.

Scenario

Your task

Write count_right_triples(rods).

rods[i] is the length of the i-th rod in millimetres. The list is not sorted, and lengths may repeat.
A triple is three different positions in the list. Call their lengths a, b and c, with c the longest.
The triple forms a frame when a * a + b * b == c * c.
Return the number of triples that form a frame. Return 0 if there is none.

Examples

Example 1 (traced)#

text2 lines

Input:  rods = [12, 5, 3, 13, 5, 4]
Output: 4

c (at k)	lo	hi	a, b	a² + b²	c²	Action	count after
5 (k = 2)	0	1	3, 4	25	25	match: 1 rod of 3, 1 rod of 4, so add 1	1
5 (k = 3)	0	2	3, 5	34	25	too much: hi becomes 1	1
5 (k = 3)	0	1	3, 4	25	25	match: add 1	2
12 (k = 4)	0	3	3, 5	34	144	too little: lo becomes 1	2
12 (k = 4)	1	3	4, 5	41	144	too little: lo becomes 2	2
12 (k = 4)	2	3	5, 5	50	144	too little: lo becomes 3, the walk ends	2
13 (k = 5)	0	4	3, 12	153	169	too little: lo becomes 1	2
13 (k = 5)	1	4	4, 12	160	169	too little: lo becomes 2	2
13 (k = 5)	2	4	5, 12	169	169	match: 2 rods of 5, 1 rod of 12, so add 2	4

The four frames are the rods 3, 4, 5 with either rod of length 5, and the rods 5, 12, 13 with either rod of length 5.

Example 2#

text2 lines

Input:  rods = [6, 8, 10, 10, 10]
Output: 3

The rods 6, 8, 10 form a frame. Any of the three rods of length 10 can be the longest, so there are three frames.

Example 3#

text2 lines

Input:  rods = [5, 6, 7, 8, 9]
Output: 0

No two rods have squares that add up to the square of a third.

Constraints

1 ≤ rods.length ≤ 3,000 (rods on the shelf)
1 ≤ rods[i] ≤ 10,000 (lengths in millimetres)

What does n ≤ 3,000 tell you?

A square can reach 10^8, and the sum of two squares 2 × 10^8, which fits in 32 bits. The count can reach about 10^9 when 1,000 rods share each of three lengths, so the answer is a 64-bit integer.