CareerCup

sort the array first or is it already sorted?

brute force: ( can b optimized)
1.sort the array (nlogn)
2.for every pair in the array, compute sqrt(num1^2+num2^2). do a binary search for this value (n^2 * logn)

total complexity:
O(nlogn + (n^2)logn) ==> O((n^2)logn)

How about using a hashmap?

Make an auxillary array b
such that
b[i]=a[i]*a[i]


Now there was a problem in which we are given a sorted array and we need to find all pair that sum up to x.

Now we can take x for each array index.

So total complexity would be O(n*n)

Now this problem reduces to a problem where we are provided a sorted array and we need to find all pair such

<pre lang="java" line="1" title="CodeMonkey20156" class="run-this">#!/usr/bin/env python

a = [-1, 2, 4, -3, 5, 10]

b = [x*x for x in a]

b = sorted(b)
print b

for x in reversed(b):
left = 0
right = len(b)-1
while not left is right:
tmp = b[left]+b[right]
if tmp is x:
print b[left], b[right], x
break
elif tmp > x:
right -= 1
else:
left += 1
</pre><pre title="CodeMonkey20156" input="yes">
</pre>

I thought of one more solution , which is first to take all the elements and put them one by one into a hash table , and then run 2 loops , taking a[i] and a[j] and computing the value of sqrt(a[i]^2 + a[j]^2) and find the resulting elements in the hash table , if they are found they form the triplet , so it takes an overall time of

O(n) {to hash all the elements} + O(n^2) {to run the loop and check for the elements from the triplet} ...

Because I feel if u already do a square and then sort u might loose the triplets like 3,4,5 and 3,4,-5 ..

suggestions / modifications are welcome.

HI ALL
i have striked something else like first we should put all odd numbers on one side and even on another o(n)
then square them o(n)
then if we analyse all even squars ends in either 0,4,6 and odd in 1,5,9
so we can further arrange in o(n)
Further with 0 all numbers will themselves be the pairs like 4+0=4 so we are leaving zero now will see further depending on question requirement
now for 1)odd+odd=even 2)even +even =even 3)even+odd=odd we wil apply these will looking for match
i do not know how to calculate last step time complexity and what could be the next best approach
any suggestions........and feedback

Further we can use hashing, but how is not clear right now

Below is the java code. Complexity in O(n^2). and It uses O(n) extra space. If anyone is able to do it in less than this, please post the soln here:

public class Triplets {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int arr[] = {3, -4, 6, 2, 5, 24, 28, 25, 7};
		findTriplets(arr);
	}

	private static void findTriplets(int arr[]) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>(arr.length);
		
		for(int i = 0; i < arr.length; i++) {
			map.put(arr[i]*arr[i], arr[i]);
		}
		
		for(int i = 0; i < arr.length; i++) {
			for(int j = i+1; j <arr.length; j++) {
				int key = arr[i]*arr[i] + arr[j]*arr[j];
				Integer val = map.get(key);
				if(val != null) {
					System.out.println("(" + arr[i] + ", " + arr[j] + ", " + val + ")");
				}
			}
		}
	}
}