How to find pythagorean triplets in an array faster than O(N^2)?

Can someone suggest an algorithm that finds all Pythagorean triplets among numbers in a given array? If it's possible, please, suggest an algorithm faster than O(n²).

Pythagorea开发者_如何学Pythonn triplet is a set {a,b,c} such that a² = b² + c². Example: for array [9, 2, 3, 4, 8, 5, 6, 10] the output of the algorithm should be {3, 4, 5} and {6, 8, 10}.

I understand this question as

Given an array, find all such triplets i,j and k, such that a[i]² = a[j]²+a[k]²

The key idea of the solution is:

• Square each element. (This takes O(n) time). This will reduce the original task to "find three numbers in array, one of which is the sum of other two".

Now it you know how to solve such task in less than O(n²) time, use such algorithm. Out of my mind comes only the following O(n²) solution:

1. Sort the array in ascending order. This takes O(n log n).

2. Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i.

   To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that's one of the answers, print it, and shift both indexes.

   This takes O(i) operations.

3. Repeat step 2 for each index i. This way you'll need totally O(n²) operations, which will be the final estimate.

No one knows how to do significantly better than quadratic for the closely related 3SUM problem ( http://en.wikipedia.org/wiki/3SUM ). I'd rate the possibility of a fast solution to your problem as unlikely.

The 3SUM problem is finding a + b + c = 0. Let PYTHTRIP be the problem of finding a^2 + b^2 = c^2 when the inputs are real algebraic numbers. Here is the O(n log n)-time reduction from 3SUM to PYTHTRIP. As ShreevatsaR points out, this doesn't exclude the possibility of a number-theoretic trick (or a solution to 3SUM!).

First we reduce 3SUM to a problem I'll call 3SUM-ALT. In 3SUM-ALT, we want to find a + b = c where all array entries are nonnegative. The finishing reduction from 3SUM-ALT to PYTHTRIP is just taking square roots.

To solve 3SUM using 3SUM-ALT, first eliminate the possibility of triples where one of a, b, c is zero (O(n log n)). Now, any satisfying triple has two positive numbers and one negative, or two negative and one positive. Let w be a number greater than three times the absolute value of any input number. Solve two instances of 3SUM-ALT: one where all negative x are mapped to w - x and all positive x are mapped to 2w + x; one where all negative x are mapped to 2w - x and all positive x are mapped to w + x. The rest of the proof is straightforward.

I have one more solution,

//sort the array in ascending order 
//find the square of each element in the array

//let 'a' be the array containing square of each element in ascending order 

for(i->0 to (a.length-1))
  for (j->i+1 to  (a.length-1))
    //search the a[i]+a[j] ahead in the array from j+1 to the end of array
      //if found get the triplet according to sqrt(a[i]),sqrt(a[j]) & sqrt(a[i]+a[j])
  endfor
endfor

Not sure if this is any better but you can compute them in time proportional to the maximum value in the list by just computing all possible triples less than or equal to it. The following Perl code does. The time complexity of the algorithm is proportional to the maximum value since the sum of inverse squares 1 + 1/2^2 + 1/3^3 .... is equal to Pi^2/6, a constant.

I just used the formula from the Wikipedia page for generating none unique triples.

my $list = [9, 2, 3, 4, 8, 5, 6, 10];
pythagoreanTriplets ($list);

sub pythagoreanTriplets
{
  my $list = $_[0];
  my %hash;
  my $max = 0;
  foreach my $value (@$list)
  {
    $hash{$value} = 1;
    $max = $value if ($value > $max);
  }
  my $sqrtMax = 1 + int sqrt $max;

  for (my $n = 1; $n <= $sqrtMax; $n++)
  {
    my $n2 = $n * $n;
    for (my $m = $n + 1; $m <= $sqrtMax; $m++)
    {
      my $m2 = $m * $m;
      my $maxK = 1 + int ($max / ($m2 + $n2));
      for (my $k = 1; $k <= $maxK; $k++)
      {
        my $a = $k * ($m2 - $n2);
        my $b = $k * (2 * $m * $n);
        my $c = $k * ($m2 + $n2);
        print "$a $b $c\n" if (exists ($hash{$a}) && exists ($hash{$b}) && exists ($hash{$c}));
      }
    }
  }
}

Here's a solution which might scale better for large lists of small numbers. At least it's different ;v) .

According to http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple,

a = m^2 - n^2, b = 2mn, c = m^2 + n^2 

b looks nice, eh?

• Sort the array in O(N log N) time.
• For each element b, find the prime factorization. Naively using a table of primes up to the square root of the largest input value M would take O(sqrt M/log M) time and space* per element.
• For each pair (m,n), m > n, b = 2mn (skip odd b), search for m^2-n^2 and m^2+n^2 in the sorted array. O(log N) per pair, O(2^(Ω(M))) = O(log M)** pairs per element, O(N (log N) (log M)) total.

Final analysis: O( N ( (sqrt M/log M) + (log N * log M) ) ), N = array size, M = magnitude of values.

(* To accept 64-bit input, there are about 203M 32-bit primes, but we can use a table of differences at one byte per prime, since the differences are all even, and perhaps also generate large primes in sequence on demand. To accept 32-bit input, a table of 16-bit primes is needed, which is small enough to fit in L1 cache. Time here is an overestimate assuming all prime factors are just less than the square root.)

(** Actual bound lower because of duplicate prime factors.)

Solution in O(N).

1. find out minimum element in array. min O(n).
2. find out maximum element in array. max O(n).
3. make a hastable of elements so that element can be searched in O(1).
4. m^2-1 = min .... put min from step 1. find out m in this equation.O(1)
5. 2m = min .... put min from step 1. find out m in this equation.O(1)

6. m^2+1= max .... put max from step 2. find out m in this equation.O(1)

7. choose floor of min of (steps 4,5,6) let say minValue.O(1)

8. choose ceil of max of (steps 4,5,6) let say maxValue.O(1)

9. loop from j=minValue to maxValue. maxvalue-minvalue will be less than root of N. 9.a calculate three numbers j^2-1,2j,j^2+1. 9.b search these numbers in hashtable. if found return success.

10. return failure.

A few of my co-workers were asked this very same problem in a java cert course they were taking the solution we came up with was O(N^2). We shaved off as much of the problem space as we could but we could not find a way to drop the complexity to N Log N or better.

    public static List<int[]> pythagoreanTripplets(int[] input) {
    List<int[]> answers = new ArrayList<int[]>();
    Map<Long, Integer> map = new HashMap<Long, Integer>();

    for (int i = 0; i < input.length; i++) {
        map.put((long)input[i] * (long)input[i], input[i]);
    }

    Long[] unique = (Long[]) map.keySet().toArray(new Long[0]);
    Arrays.sort(unique);
    long comps =0;
    for(int i =  1 ; i < unique.length;i++)
    {
        Long halfC = unique[i]/2;
        for(int j = i-1 ; j>= 0 ; j--)
        {

            if(unique[j] < halfC) break;
            if(map.containsKey(unique[i] - unique[j]))
            {
                answers.add(new int[]{map.get(unique[i] - unique[j]),map.get(unique[j]),map.get(unique[i])});
            }
        }
    }
    return answers;
}

If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer.

so simply find one value for a, b, and c and then you can calculate as many new ones as you want.

Pseudo code:

a = 3
b = 4
c = 5
for k in 1..N:
  P[k] = (ka, kb, kc)

Let me know if this is not exactly what you're looking for.

It can be done in O(n) time. first hash the elements in map for existence check. after that apply the below algorithm

Scan the array and if element is even number, (n,n^2/2 +1, n^2/2 -1) is triplet to be found. just check for that's existence using hash map lookup. if all elements in triplet exists, print the triplet.

This is the one i had implemented ...

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


/**
 * 
 * @author Pranali Choudhari (pranali_choudhari@persistent.co.in)
 */
public class PythagoreanTriple {

/
    //I hope this is optimized



    public static void main(String[] args) {

        Map<Long,Set<Long>> triples = new HashMap<Long,Set<Long>>();
        List<Long> l1 = new ArrayList<Long>();
        addValuesToArrayList(l1);
        long n =0;        
        for(long i : l1){
            //if its side a.
             n = (i-1L)/2L;
             if (n!=0 && n > 0){
                  putInMap(triples,n,i);
                  n=0;
             }
             //if its side b 

             n = ((-1 + Math.round(Math.sqrt(2*i+1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             n=  ((-1 - Math.round(Math.sqrt(2*i+1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             //if its side c

             n = ((-1 + Math.round(Math.sqrt(2*i-1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }
             n=  ((-1 - Math.round(Math.sqrt(2*i-1)))/2);
             if (n != 0 && n > 0){
                 putInMap(triples,n,i);
                  n=0;
             }


        }
        for(Map.Entry<Long, Set<Long>> e : triples.entrySet()){
            if(e.getValue().size() == 3){
                System.out.println("Tripples" + e.getValue());
            }
            //need to handle scenario when size() > 3 
            //even those are tripples but we need to filter the wrong ones
        }


    }

    private static void putInMap( Map<Long,Set<Long>> triples, long n,  Long i) {
        Set<Long> set = triples.get(n);
        if(set == null){
            set = new HashSet<Long>();
            triples.put(n, set);
        }
        set.add(i);
    }

    //add values here 
    private static void addValuesToArrayList(List<Long> l1) {
        l1.add(1L);
        l1.add(2L);
        l1.add(3L);
        l1.add(4L);
        l1.add(5L);
        l1.add(12L);
        l1.add(13L);

    }
}

Here's the implementation in Java:

/**
 * Step1: Square each of the elements in the array [O(n)]
 * Step2: Sort the array [O(n logn)]
 * Step3: For each element in the array, find all the pairs in the array whose sum is equal to that element [O(n2)]
 * 
 * Time Complexity: O(n2) 
 */
public static Set<Set<Integer>> findAllPythogoreanTriplets(int [] unsortedData) {

    // O(n) - Square all the elements in the array
    for (int i = 0; i < unsortedData.length; i++)
        unsortedData[i] *= unsortedData[i];

    // O(n logn) - Sort
    int [] sortedSquareData = QuickSort.sort(unsortedData);

    // O(n2)
    Set<Set<Integer>> triplets = new HashSet<Set<Integer>>();

    for (int i = 0; i < sortedSquareData.length; i++) {

        Set<Set<Integer>> pairs = findAllPairsThatSumToAConstant(sortedSquareData, sortedSquareData[i]);

        for (Set<Integer> pair : pairs) {
            Set<Integer> triplet = new HashSet<Integer>();
            for (Integer n : pair) {
                triplet.add((int)Math.sqrt(n));
            }
            triplet.add((int)Math.sqrt(sortedSquareData[i])); // adding the third element to the pair to make it a triplet
            triplets.add(triplet);
        }
    }

    return triplets;
}


public static Set<Set<Integer>> findAllPairsThatSumToAConstant(int [] sortedData, int constant) {

    // O(n)
    Set<Set<Integer>> pairs = new HashSet<Set<Integer>>();
    int p1 = 0; // pointing to the first element
    int p2 = sortedData.length - 1; // pointing to the last element
    while (p1 < p2) {
        int pointersSum = sortedData[p1] + sortedData[p2];
        if (pointersSum > constant)
            p2--;
        else if (pointersSum < constant)
            p1++;
        else {
            Set<Integer> set = new HashSet<Integer>();
            set.add(sortedData[p1]);
            set.add(sortedData[p2]);
            pairs.add(set);
            p1++;
            p2--;
        }
    }
    return pairs;
}

if the problem is the one "For an Array of integers find all triples such that a^2+b^2 = c^2

Sort the array into ascending order

Set three pointers p1,p2,p3 at entries 0,1,2 set pEnd to past the last entry in the array

while (p2 < pend-2) {

sum = (*p1 * *p1 + *p2 * *p2)


while ((*p3 * *p3) < sum && p3 < pEnd -1)
   p3++;

if ( *p3 == sum) 
   output_triple(*p1, *p2, *p3);

p1++;
p2++;

}

it's moving 3 pointers up the array so it O(sort(n) + n) it's not n2 because the next pass starts at the next largest number and doesn't reset. if the last number was too small for the triple, it's still to small when you go to the next bigger a and b

public class FindPythagorusCombination {

    public static void main(String[] args) {
        int[] no={1, 5, 3, 4, 8, 10, 6 };
        int[] sortedno= sorno(no);
        findPythaComb(sortedno);
    }

    private static void findPythaComb(int[] sortedno) {
        for(int i=0; i<sortedno.length;i++){

            int lSum=0, rSum=0;
            lSum= sortedno[i]*sortedno[i];
            for(int j=i+1; j<sortedno.length; j++){
                for(int k=j+1; k<sortedno.length;k++){
                    rSum= (sortedno[j]*sortedno[j])+(sortedno[k]*sortedno[k]);
                    if(lSum==rSum){
                        System.out.println("Pythagorus combination found: " +sortedno[i] +" " +sortedno[j]+" "+sortedno[k]);
                    }else
                        rSum=0;
                }

            }
        }
    }

    private static int[] sorno(int[] no) {

        for(int i=0; i<no.length;i++){

            for(int j=i+1; j<no.length;j++){
                if(no[i]<no[j]){
                    int temp= no[i];
                    no[i]= no[j];
                    no[j]=temp;
                }
            }

        }

        return no;

    }



}

    import java.io.*;
import java.lang.*;
import java.util.*;

class PythagoreanTriplets
{
 public static void main(String args[])throws IOException
 {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  int n = Integer.parseInt(br.readLine());
  int arr[] = new int[n];
  int i,j,k,sum;
  System.out.println("Enter the numbers ");
  for(i=0;i<n;i++)
   {
    arr[i]=Integer.parseInt(br.readLine());
    arr[i]=arr[i]*arr[i];
   }
Arrays.sort(arr);
  for(i=n-1;i>=0;i--)
   {
     for(j=0,k=i-1;j<k;)
        {  
          sum=arr[j]+arr[k];
          if(sum==arr[i]){System.out.println((int)Math.sqrt(arr[i]) +","+(int)Math.sqrt(arr[j])+","+(int)Math.sqrt(arr[k]));break;}
          else if(sum>arr[i])k--;
          else j++;

        }
   }

}
}

Finding Pythagorean triplets in O(n)

Algorithm:

1. For each element in array, check it is prime or not
2. if it is prime, calculate other two number as ((n^2)+1)/2 and ((n^2)-1)/2 and check whether these two calculated number is in array
3. if it is not prime, calculate other two number as mentioned in else case in code given below

4. Repeat until end of array is reached

    int arr[]={1,2,3,4,5,6,7,8,9,10,12,13,11,60,61};
    int prim[]={3,5,7,11};//store all the prime numbers
    int r,l;
    List<Integer> prime=new ArrayList<Integer>();//storing in list,so that it is easy to search
    for(int i=0;i<4;i++){
     prime.add(prim[i]);
    }
    List<Integer> n=new ArrayList<Integer>();
    for(int i=0;i<arr.length;i++)
    {
           n.add(arr[i]);
    }
    double v1,v2,v3;
    int dummy[]=new int[arr.length];
    for(int i=0;i<arr.length;i++)
       dummy[i]=arr[i];
   
    Integer x=0,y=0,z=0;
    List<Integer> temp=new ArrayList<Integer>();
    for(int i=0;i<arr.length;i++)
    {
        temp.add(arr[i]);
    }
   
    for(int j:n){
       if(prime.contains(j)){//if it is prime
           double a,b; 
           v1=(double)j;
           v2=Math.ceil(((j*j)+1)/2);
           v3=Math.ceil(((j*j)-1)/2);
           if(n.contains((int)v2) && n.contains((int)v3)){
             System.out.println((int)v1+" "+(int)v2+" "+(int)v3);
           }
       }
       else//if it is not prime
       {
            if(j%3==0){
               x=j;
               y=4*(j/3);
               z=5*(j/3);
               if(temp.contains(y) && temp.contains(z)){
                       System.out.println(x+" "+y+" "+z);
                       //replacing those three elements with 0
                       dummy[temp.indexOf(x)-1]=0;
                       dummy[temp.indexOf(y)-1]=0;
                       dummy[temp.indexOf(z)-1]=0;
               }
            }   
       }//else end
   }//for end
   

Complexity: O(n)

Take a look at the following code that I wrote.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

bool existTriplet(vector<ll> &vec)
{
    for(auto i = 0; i < vec.size(); i++)
    {
        vec[i] =  vec[i] * vec[i]; //Square all the array elements
    }

    sort(vec.begin(), vec.end()); //Sort it
    for(auto i = vec.size() - 1; i >= 2; i--)
    {
        ll l = 0;
        ll r = i - 1;
        while(l < r)
        {
            if(vec[l] + vec[r] == vec[i])
                return true;

            vec[l] + vec[r] < vec[i] ? l++ : r--;
        }
    }
    return false;
}
int main() {
    int T;
    cin >> T;
    while(T--)
    {
        ll n;
        cin >> n;
        vector<ll> vec(n);
        for(auto i = 0; i < n; i++)
        {
            cin >> vec[i];
        }
        if(existTriplet(vec))
            cout << "Yes";
        else
            cout << "No";
        cout << endl;
    }
    return 0;
}

Plato's formula for Pythagorean Triples: Plato, a Greek Philosopher, came up with a great formula for finding Pythagorean triples.

(2m)^2 + (m^2 - 1)^2 = (m^2 + 1)^2

bool checkperfectSquare(int num){
    int sq=(int)round(sqrt(num));
    if(sq==num/sq){
        return true;
    }
    else{
        return false;
    }
}

void solve(){
    int i,j,k,n;

    // lenth of array
    cin>>n;
    int ar[n];
    // reading all the number in array
    for(i=0;i<n;i++){
        cin>>ar[i];
     }
    // sort the array
    sort(ar,ar+n);
    for(i=0;i<n;i++){
        if(ar[i]<=2){
            continue;
        }
        else{
            int tmp1=ar[i]+1;
            int m;
            if(checkperfectSquare(tmp1)){
                m=(ll)round(sqrt(tmp1));
                int b=2*m,c=(m*m)+1;
                if(binary_search(ar,ar+n,b)&&binary_search(ar,ar+n,c)){
                    cout<<ar[i]<<" "<<b<<" "<<c<<endl;
                    break;
                }
            }
            if(ar[i]%2==0){
                m=ar[i]/2;
                int b=(m*m-1),c=(m*m+1);
                if(binary_search(ar,ar+n,b)&&binary_search(ar,ar+n,c)){
                    cout<<ar[i]<<" "<<b<<" "<<c<<endl;
                    break;
                }
            }
        }
    }
}