Pythagorean triplets

Computer Science Level 3

Pythagorean triplets are triplets that satisfy the condition that a 2 + b 2 = c 2 a^{2}+b^{2}=c^{2} such that a < b < c a<b<c . Given an unsorted array of unique integers in the text file, how many Pythagorean triplets are there?

As an explicit example, in the array [ 3 , 7 , 10 , 6 , 4 , 8 , 5 , 11 ] [3,7,10,6,4,8,5,11] , there are 2 2 Pythagorean Triplets, namely ( 3 , 4 , 5 ) (3, 4, 5) and ( 8 , 6 , 10 ) (8, 6, 10) .


The answer is 207.

Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Thaddeus Abiy
Aug 4, 2015

The python set is essentially a hashmap. Because of the nature of this data struture, checking if an object is within it takes a snappy ( O ( 1 ) O(1) ) time. I then just go through every pair a , b a,b and check if a 2 + b 2 \sqrt{a^2 + b^2} is in L . 0 0 is initially removed from the set. If it hadn't been we would admit solutions such as a , 0 , a a,0,a . Thanks to itertools and the integer nature of booleans in python, the actual solution can be reduced to a concise one liner that runs in O ( n 2 ) O(n^2) . 

1
2
3
 
from itertools import combinations as combo
L = set([196, 17, 32, 222, 35, 247, 95, 267, 197, 71, 42, 11, 44, 251, 18, 194, 172, 28, 108, 216, 125, 55, 103, 259, 66, 75, 163, 20, 122, 64, 147, 52, 127, 298, 58, 153, 33, 110, 76, 140, 113, 157, 294, 165, 142, 187, 211, 149, 265, 81, 244, 293, 286, 156, 130, 132, 112, 284, 14, 143, 288, 105, 83, 292, 266, 217, 299, 181, 5, 106, 131, 203, 158, 243, 275, 295, 198, 176, 236, 252, 224, 92, 129, 272, 43, 195, 167, 10, 206, 164, 135, 212, 77, 65, 133, 84, 174, 280, 104, 23, 229, 145, 297, 264, 59, 289, 96, 31, 144, 263, 57, 249, 134, 154, 233, 34, 245, 239, 29, 258, 278, 53, 215, 117, 283, 124, 100, 86, 72, 182, 26, 114, 208, 204, 237, 88, 136, 148, 276, 235, 257, 209, 80, 169, 120, 62, 24, 46, 16, 41, 201, 287, 238, 3, 116, 188, 54, 70, 254, 78, 82, 2, 63, 37, 226, 281, 277, 68, 48, 138, 118, 205, 232, 137, 207, 115, 1, 139, 85, 218, 160, 183, 186, 128, 214, 97, 223, 67, 60, 260, 171, 13, 199, 109, 162, 253, 200, 73, 141, 179, 21, 38, 180, 91, 191, 175, 256, 279, 255, 9, 12, 241, 221, 177, 248, 89, 119, 49, 193, 189, 228, 27, 40, 93, 51, 220, 296, 240, 126, 271, 173, 219, 227, 61, 19, 111, 50, 213, 94, 161, 87, 98, 30, 231, 74, 150, 192, 152, 79, 22, 185, 47, 107, 159, 261, 8, 7, 178, 146, 39, 151, 234, 190, 285, 4, 25, 268, 242, 155, 262, 270, 56, 6, 36, 184, 290, 69, 101, 15, 170, 102, 123, 225, 45, 282, 250, 210, 168, 90, 273, 274, 291, 246, 0, 166, 99, 269, 121, 230, 202]).difference(set([0]))
print sum((a*a+b*b)**.5 in L for a,b in combo(L,2))

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Bill Bell
Aug 4, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
source=[196, 17, 32, 222, 35, 247, 95, 267, 197, 71, 42, 11, 44, 251, 18, 194, 172, 28, 108, 216, 125, 55, 103, 259, 66, 75, 163, 20, 122, 64, 147, 52, 127, 298, 58, 153, 33, 110, 76, 140, 113, 157, 294, 165, 142, 187, 211, 149, 265, 81, 244, 293, 286, 156, 130, 132, 112, 284, 14, 143, 288, 105, 83, 292, 266, 217, 299, 181, 5, 106, 131, 203, 158, 243, 275, 295, 198, 176, 236, 252, 224, 92, 129, 272, 43, 195, 167, 10, 206, 164, 135, 212, 77, 65, 133, 84, 174, 280, 104, 23, 229, 145, 297, 264, 59, 289, 96, 31, 144, 263, 57, 249, 134, 154, 233, 34, 245, 239, 29, 258, 278, 53, 215, 117, 283, 124, 100, 86, 72, 182, 26, 114, 208, 204, 237, 88, 136, 148, 276, 235, 257, 209, 80, 169, 120, 62, 24, 46, 16, 41, 201, 287, 238, 3, 116, 188, 54, 70, 254, 78, 82, 2, 63, 37, 226, 281, 277, 68, 48, 138, 118, 205, 232, 137, 207, 115, 1, 139, 85, 218, 160, 183, 186, 128, 214, 97, 223, 67, 60, 260, 171, 13, 199, 109, 162, 253, 200, 73, 141, 179, 21, 38, 180, 91, 191, 175, 256, 279, 255, 9, 12, 241, 221, 177, 248, 89, 119, 49, 193, 189, 228, 27, 40, 93, 51, 220, 296, 240, 126, 271, 173, 219, 227, 61, 19, 111, 50, 213, 94, 161, 87, 98, 30, 231, 74, 150, 192, 152, 79, 22, 185, 47, 107, 159, 261, 8, 7, 178, 146, 39, 151, 234, 190, 285, 4, 25, 268, 242, 155, 262, 270, 56, 6, 36, 184, 290, 69, 101, 15, 170, 102, 123, 225, 45, 282, 250, 210, 168, 90, 273, 274, 291, 246, 0, 166, 99, 269, 121, 230, 202]
source.remove(0)
source.sort()
squares={s**2:s for s in source}

def squarePairs():
    for i,s in enumerate(source[:-1]):
        for t in source[i+1:]:
            yield (s**2+t**2,s,t)

count=0
previous=[0,0,0]
for sp in squarePairs():
    if sp[0] in squares.keys():
        sides=sp[1], sp[2], squares[sp[0]]
        if sides==previous:
            continue
        previous=sides
        count+=1
print count

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
Aug 7, 2015

Inefficient way - 

1
2
3
4
5
6
7
 
>>> import itertools
>>> x = itertools.permutations([... That array], 3)
>>> count = 0
>>> for n in x:
        if n[0] ** 2 + n[1] ** 2 == n[2] ** 2:
            count += 1
>>> print count / 2

A better approach would be to use combinations. I'll code that later.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...