## Square Triple

### February 14, 2020

Our algorithm finds all pairs, then checks if the square root of the product is in the list:

```(define (f xs)
(list-of (list x y z)
(x in xs)
(y in xs)
(< x y)
(z2 is (* x y))
(z is (isqrt z2))
(= (* z z) z2)
(member z xs)))```

We eliminate duplicates by insisting that x < y. Here’s an example:

```> (f (range 1 20))
((1 4 2) (1 9 3) (1 16 4) (2 8 4) (2 18 6) (3 12 6) (4 9 6)
(4 16 8) (8 18 12) (9 16 12))```

That takes time O(n³); n * n to form the pairs and another factor of n to search the list. We could reduce that to O(n²) by first inserting the list items in a hash table and checking membership there. Another improvement is a quick exit if the product exceeds the maximum list item. We’ll leave those improvements as an exercise to the reader.

You can run the program at https://ideone.com/L7itmh.

Pages: 1 2

### 12 Responses to “Square Triple”

1. James Smith said

Easiest way to make this o(n2) is to first compute an array of squares and use this to filter results… as usual in Perl…

```use strict;
use feature qw(say);

my @ints = 1..50;                                ## Test data...

my %squares = map { \$_*\$_ => \$_ } @ints;         ## Use hash to store possible squares (value is sqrt)

say map {
my \$a = \$_;                                    ## Nested map store copy of outer key...
map  { join ',', \$a, \$_, \$squares{\$a*\$_}.' ' } ## Display three values - sqrt is value of hash keyed by square
grep { exists \$squares{\$a*\$_}                } ## Now check to see if the product is a square..
grep { \$a < \$_                               } ## Quick filter only want 1st no < 2nd no
@ints
} @ints;
```
2. matthew said

Here’s an O(n²) solution that doesn’t require any auxiliary storage. Assumes input is sorted and all positive:

```# If ab = z^2 with a != b, can assume a < z < b, so
# keep 2 pointers into the list and keep track of the
# product of values pointed to - if too high, the lower
# pointer needs to be increased, if too low, the higher:

def triples(a):
n = len(a)
for i in range(1,n-1):
target = a[i]*a[i]
j,k = i-1,i+1
while j >= 0 and k < n:
product = a[j]*a[k]
if product > target: j = j-1
elif product < target: k = k+1
else:
yield(a[j],a[k],a[i])
j,k = j-1,k+1

# [(1, 4, 2), (1, 9, 3), (1, 16, 4), (2, 8, 4), (2, 18, 6),
#  (3, 12, 6), (4, 9, 6), (4, 16, 8), (8, 18, 12), (9, 16, 12)]
print(sorted(list(triples(range(1,20)))))
```
3. Zack said

Here is my approach to the problem using Julia, as usual: https://pastebin.com/FjqkHhQ7

Although I iterate through the data points using a triple loop, not all combinations are examined since I take advantage of the fact that the integers are distinct (so there is one zero at most), simplifying the whole process. Cheers!

4. Daniel said

Here’s a O(n^2) solution in Python.

I’ve assumed x, y, z are distinct (e.g., no (x=1,y=1,z=1) nor (x=0, y=2, z=0)), which I think is suggested by the problem specifying a “list of distinct integers” for the input.

```from collections import defaultdict

def square_triple(input):
output = []
roots = defaultdict(list)
for x in input:
roots[x * x].append(x)
for x in input:
for y in input:
if x == y: continue
for z in roots[x * y]:
if x != z and y != z:
output.append((x, y, z))
return output

for triple in square_triple(range(-8, 9)):
print(triple)
```

Output:

```(-8, -2, -4)
(-8, -2, 4)
(-4, -1, -2)
(-4, -1, 2)
(-2, -8, -4)
(-2, -8, 4)
(-1, -4, -2)
(-1, -4, 2)
(1, 4, -2)
(1, 4, 2)
(2, 8, -4)
(2, 8, 4)
(4, 1, -2)
(4, 1, 2)
(8, 2, -4)
(8, 2, 4)
```
5. Daniel said

@programmingpraxis, I think that using square roots for this problem can be problematic, since as-is it won’t handle negative values for z.

6. Daniel said

(where “square roots” in my comment refers to the conventional function that returns a single non-negative value)

7. Steve said

Klong version

```        :" Number from 1 to 20"
list::1+!20
[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

:" Get all pairs of number in list"
pairs::{x,:\list}'list
[[[1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10]...]]

:" Flatten the list"
l::,/pairs::{x,:\list}'list
[[1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10] [1 11] [1 12] [1 13] [1 14] [1 15] ...]

:" Only those pairs where the first # < second #
l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list
[[1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10] [1 11] [1 12] [1 13] [1 14] [1 15]...]

:" Only those pairs where product is square of one of the number in the list"
l::l@&{#sqrs?*/x}'l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list
[[1 4] [1 9] [1 16] [2 8] [2 18] [3 12] [4 1] [4 9] [4 16] [5 20] [8 2] [8 18] [9 1] [9 4] [9 16] [12 3] [16 1] [16 4] [16 9] [18 2] [18 8] [20 5]]

:" Get rid of duplicates"
l@&{(x@0)<x@1}'l::l@&{#sqrs?*/x}'l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list
[[1 4] [1 9] [1 16] [2 8] [2 18] [3 12] [4 9] [4 16] [5 20] [8 18] [9 16]]

:" Add square root of product"
{x,_(*/x)^0.5}'l@&{(x@0)<x@1}'l::l@&{#sqrs?*/x}'l::l@&{~(x@0)=x@1}'l::,/pairs::{x,:\list}'list
[[1 4 2] [1 9 3] [1 16 4] [2 8 4] [2 18 6] [3 12 6] [4 9 6] [4 16 8] [5 20 10] [8 18 12] [9 16 12]]

```
8. Richard A. O'Keefe said

The problem says to find ALL triples, but the model answer finds only half of them.
Nothing whatsoever in the problem says that the numbers are all positive or all non-negative.
In fact by using “integer” instead of “natural number” it suggests that negative numbers are allowed.
Given [-2,1,2,4], (1,4,2) and (1,4,-2) are both legal triples, but the model answer will not find the second.

9. Steve said

I thought it might be interesting to explain some of the facilities of the Klong programming language. I like to learn this about other languages – they all seem to have their strengths – and Klong is one of the more unusual ones I’ve come upon.

``````    !20 yields the list of numbers from 0 to 19
``````

[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]

``````    Add 1 to each member of that list
list::1+!20
``````

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

``````    Append 1 to the left of each member of the list
1,:\list
``````

[[1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7] [1 8] [1 9] [1 10] [1 11] [1 12] [1 13] [1 14] [1 15] [1 16] [1 17] [1 18] [1 19] [1 20]]

``````    Tick ("'") applies a function to each member of a list
{x+3}'[1 2 3]
``````

[4 5 6]

``````    "@&" acts as a filter on a list
Filter the list where the element mod 2 = 1
list@&{1=x!2}'list
``````

[1 3 5 7 9 11 13 15 17 19]

``````    "?" tests for membership in a list and "/" applies an operator over a list
[1 2 3]?1
``````

[0]
[1 2 3]?4
[]
*/[2 3]
6

10. Steve said

Richard noticed that the example solution did not find all solutions. Mine didn’t either. Here’s version 2 for Klong.

```        list::[-2 1 2 4]
[-2 1 2 4]

pairs::pairs@&{~(x@0)=x@1}'pairs::,/{x,:\list}'list
[[-2 1] [-2 2] [-2 4] [1 -2] [1 2] [1 4] [2 -2] [2 1] [2 4] [4 -2] [4 1] [4 2]]

{(x@1),(x@2),x@0}'triples@&{(x@1)<x@2}'triples::triples@&{((x@0)^2)=((x@1)*x@2)}'triples::,/{x,:\pairs}'list
[[1 4 -2] [1 4 2]]

```
11. Anon said

This is a common lisp solution. It assumes the input list is sorted in accending order.

```(defun sol (ns)
(flet ((fn (xs)
(let ((x (car xs))
(ys (cdr xs))
(res nil))
(dolist (y ys res)
(let ((z (sqrt (* x y))))
(when (find z ys :test #'=)
(push (list x y (ceiling z)) res)))))))
(mapcon #'fn ns)))
```

Sample run:

```CL-USER> (sol (loop for i from 1 to 20 collect i))
((1 16 4) (1 9 3) (1 4 2) (2 18 6) (2 8 4) (3 12 6) (4 16 8) (4 9 6) (5 20 10)
(8 18 12) (9 16 12))
```
12. Sam Claflin said

Python Solution:

def find_triples(int_list):
triples = []

# Loop through all integers in list
for k in range(len(int_list)):
for i in range(len(int_list)):
for j in range(len(int_list)):

# Detect valid pair
if int_list[k] * int_list[i] == int_list[j] ** 2:
same = False

# Check each tuple to see if different permutation of pair is already present
for tup in triples:
if int_list[k] in tup and int_list[i] in tup and int_list[j] in tup:
same = True
break
if not same:
triples.append((int_list[k], int_list[i], int_list[j]))
else:
continue
return triples

print(find_triples(range(1, 15)))

OUTPUT:

[(1, 1, 1), (1, 4, 2), (1, 9, 3), (2, 8, 4), (3, 12, 6), (4, 9, 6), (5, 5, 5), (7, 7, 7), (10, 10, 10), (11, 11, 11), (13, 13, 13), (14, 14, 14)]