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)]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: