CareerCup

1)sort the array
2)find the square of all the numbers
3)use 3SUM techinque (search 3SUM in wiki)

use tow for loops to find a2+b2 and serach for that value in the sorted array.

O(n2logn) is complexity.

otherwise, if you store n numbers in hashtable O(n2) time and O(n) space complexity.

public class PythaTriplet {
	public static void main(String[] args) {
		int [] A={2, 9, 4, 5, 3, 60, 8, 30, 33, 45, 10, 40, 7, 50, 6};
		int l=A.length;
		int []b=sortArr(A, l);
		for(int i=0; i<l; i++){
			System.out.print(b[i]+" ");
		}
		System.out.println("\n");
		//pythaTripletN3(A, l);
		pythaTripletN2(A, l);
	}
	
	static int [] sortArr(int []A, int l){
		for(int i=0; i<l; i++){
			for(int j=i+1; j<l; j++){
				if(A[i]>A[j]){
					int temp=A[i];
					A[i]=A[j];
					A[j]=temp;
				}
			}
		}
		return A;
		
	}


	//n^3
	static void pythaTripletN3(int [] A, int l){
		int c=0;
		int []B=new int [l];
		for(int i=0; i<l; i++){
			B[i]=(int) Math.pow(A[i], 2);
		}
		for(int i=0; i<l-2; i++)
			for(int j=i+1; j<l-1; j++)
				for(int k=j+1; k<l; k++)
					if(B[i]+B[j]==B[k]){
						System.out.print("("+A[i]+", "+A[j]+", "+A[k]+")"+" ");
						c++;
					}
		System.out.println("\n"+c);
	}
	

	
	//n^2
	static void pythaTripletN2(int [] A, int l){
		int c=0;
		int []B=new int[l];
		for(int i=0; i<l; i++){
			B[i]=A[i]*A[i];
		}
		for(int j=2; j<l; j++){
			int k=0, n=j-1;
			while(k<n){
				if(B[k]+B[n]==B[j]){
					System.out.print("("+A[k]+", "+A[n]+", "+A[j]+")"+" ");
					k++;
					n--;
					c++;
				}
				else if(B[k]+B[n]>B[j])
					n--;
				else
					k++;
			}
		}
		int index=c;
		System.out.print("\n\n"+"index= " +index);
	}
}


output: 
2 3 4 5 6 7 8 9 10 30 33 40 45 50 60 

(3, 4, 5) (6, 8, 10) (30, 40, 50) 

index= 3

In an array have all the square of the numbers stored, sort them and find the pair whose sum is the third number in that arrray

for (i = 0; i < N; i++)
  Arr[i] = Arr[i] * Arr[i];
for (i = 0; i < N - 2; i++)
{
  for (j = i + 1; j < N - 1; j++)
  {
    for (k = j + 1; j < N; j++)
    {
      if (Arr[i] + Arr[j] == Arr[k])
      {
        Console.WriteLine("{0}\t{1}\t{2}", Arr[i], Arr[j], Arr[k]);
        Console.WriteLine("{0}\t{1}\t{2}", i, j, k);
      }
      else if (Arr[i] + Arr[k] == Arr[j])
      {
        Console.WriteLine("{0}\t{1}\t{2}", Arr[i], Arr[j], Arr[k]);
        Console.WriteLine("{0}\t{1}\t{2}", i, j, k);
      }
      else if (Arr[k] + Arr[j] == Arr[i])
      {
        Console.WriteLine("{0}\t{1}\t{2}", Arr[i], Arr[j], Arr[k]);
        Console.WriteLine("{0}\t{1}\t{2}", i, j, k);
      }
    }
  }
}

int a[] = {1, 5, 4, 3, 9, 4, 30, 40, 25, 50};
		
		for(int i = 0; i < a.length; i++)
			a[i] *= a[i];
		
		Arrays.sort(a);
		
		if(a.length > 3)
		{
			for(int i = 2; i < a.length; i++)
			{
				int start = 0, end = i - 1;
				while(start < end)
				{
					if(a[start] + a[end] == a[i])
					{
						System.out.println(Math.sqrt(a[start]) + "^2 + " + Math.sqrt(a[end]) + "^2 = " + Math.sqrt(a[i]) + "^2");
						start++;
						end--;
					}
					else if(a[start] + a[end] < a[i])
						start++;
					else
						end--;
				}
			}
		}
	}

n^2logn

public static void pythogoreanTriplets(int[] a)
{
if (a.Length == 0)
return;
Dictionary<int, int> d = new Dictionary<int, int>();
for (int i = 0; i < a.Length; i++)
{
if (!d.ContainsKey(a[i] * a[i]))
{
d.Add(a[i] * a[i], i);
}
}

for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < a.Length; j++)
{
int sumOfTwoNum = a[i]*a[i]+a[j]*a[j];

if (d.ContainsKey(sumOfTwoNum))
{
int dIndex;
d.TryGetValue(sumOfTwoNum, out dIndex);
Console.WriteLine("Triplet Found, {0} at index {1}, {2} at index {3}, {4} at index {5}",a[i],i,a[j],j,Math.Sqrt(sumOfTwoNum),dIndex);
d.Remove(sumOfTwoNum); // this is to prevent displaying duplicate results
}
}
}
}

public static void printPythagaron() {
		int[] a = {3, 5, 7, 4, 12, 24, 11, 21, 13, 25, 8, 15, 17, 35, 37};
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < a.length; i++) {
			map.put(a[i], a[i]);
		}

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

			if (a[i] % 2 != 0) {
				int b = a[i] / 2;
				b = a[i] * b + b;
				if (map.get(b) != null) {
					if (map.get(b + 1) != null) {
						System.out.println("("+ a[i] + "," + b + "," + (b + 1) + ")");
					}
				}
			}
			if(a[i]%4 == 0){
				int b = a[i]/4;
				b = a[i]*b-1;
				if (map.get(b) != null) {
					if (map.get(b + 2) != null) {
						System.out.println("("+ a[i] + "," + b + "," + (b + 2) + ")");
					}
				}
			}

		}

}