2

Someone asked me a question(asked to him in an interview) that how to find triplets in an integer array A[] which satisfy following condition:

a[i]^2 + a[j]^2 = a[k]^2

i have done it in o(n^2 logn) can it be optimized.

algo-geeks
  • 5,280
  • 10
  • 42
  • 54
  • 1
    my approach: given an array first sort it in o(nlgn) then corresponding to each pair of (i,j) search through binary search technique for (i+j).so i think time is o(nlogn).optimizations required. – algo-geeks Dec 23 '10 at 06:03
  • Please consider saving time for your self - http://stackoverflow.com/questions/575117/pythagorean-triplets – abRao Dec 23 '10 at 06:29

2 Answers2

0

A variation of your approach that's O(n^2).

def findPythagoreanTriplets(array):
  array = sorted(array)
  for i in range(len(array)):
    k = i + 2
    for j in range(i + 1, len(array)):
      while k < len(array) and (array[k] ** 2 < (array[i] ** 2 + array[j] ** 2)):
        k += 1
      if k < len(array) and (array[k] ** 2 == (array[i] ** 2 + array[j] ** 2)):
        print "%d^2 + %d^2 = %d^2" % (array[i], array[j], array[k])

This is Python code, but converting to C shouldn't be hard. (Actually, this question seems language agnostic, so I'm not sure why you've got the c tag...)

This is assuming all of the inputs are non-negative. You could probably make it work for negative integers as well, but you'd need to sort by the squared value, not by the input value (for non-negative numbers they're the equivalent).

Instead of doing a binary search you just do a linear search for k, but you can pick up from where the previous j's search left off, so searching for k is "free".

Laurence Gonsalves
  • 137,896
  • 35
  • 246
  • 299
-1

At least you can use hash table to store squares. So search of (i^2+j^2) for each pair will be in O(1) and in overall algorithm will take O(n^2)

DixonD
  • 6,557
  • 5
  • 31
  • 52