CareerCup

Ref : en.wikipedia.org/wiki/Pythagorean_triple

you basically need to generate all primitive Pythagorean triples (PPT) from which you can generate the rest. For example, <3,4,5> is a PPT, from which you can get triples <3k, 4k, 5k> for k >= 1 and k <= n/5

How to find a PPT is explained here : en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple

Can it be done better than o(n^2) without pre-calculations of pythag triples?

If you check wikipedia 3SUM it sounds like a "hard" problem.

And for some reason this is all sounding really sexual.

Definitely not better than O(N*N) but one more solution to this problem:

A) Sort the array.
B) Now start from 3rd element (Lets keep the current pointer to third element)
- Keep two pointers. One at the beginning and one before the current element.
For example if we are at position 10. Then lets have a low pointer pointing
to first number and high pointer pointing to number 9. Check if
sqr(current) = sqr(low) + sqr(high) i.e. in this case : sqr(10th) = sqr(1st) + sqr(9th).
- if sqr(10th) = sqr(1st) + sqr(9th) then we have got the triplet, move current to 11th element.
- If sqr(1st) + sqr(9th) > sqr(10th) then decrease high and do the same ...
- If sqr(1st) + sqr(9th) < sqr(10th) then increase low and do the same ...
This logic is similar to finding two numbers in a sorted array whose sum is a given number.

The sorting will take O(N LOG (N)). Remaining logic should take O(N*N).

My little solution:
Let’s say arr={2,3,4,5,6}

Arr[0]^2=4
So 4=1+3
Sqrt(4)=Sqrt(1)+Sqrt(3)
Sqrt(4)=Sqrt(2)+Sqrt(2)
The below iteration need not cheack!! Becoz we done it in previous iterations.
Sqrt(4)=Sqrt(3)+Sqrt(1)
Like above
We’ll reach 5
Sqrt(5)=25
Sqrt(25)= Sqrt(1)+ Sqrt(24)
Sqrt(25)= Sqrt(2)+ Sqrt(23)
....
..
..
Sqrt(25)= Sqrt(9)+ Sqrt(16)
Doing the each step search for the element Sqrt(9) and Sqrt(16) in the original array Time complexity for searching an element in an array is o(n);
It You find print a,b,c
One more test case can be added if Sqrt is not perfect sqr then we can avoid searching for that element in the array.
I hope so My Solution may help !!!!
Total Time Complexity= o(n) (To traverse the array)+o(Max element in array/2)+o(n) to search for the element

use hash map

i think this can be solved it this way :
lets suppose given array is : {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
all we need is multiple of 3 , 4 and 5 ,
lets have them in different arrays {3,6,9,12,15}
{4,8,12}
{5,10,15}

now we just need to make out equations like this : 3^2 + 4^2 = 5^2
6^2 + 8 ^2 = 10^2
9^2 + 12^2 = 15^2

and i guess these are the only combinations that can result in the equation of type a^2 + b^2 = c^2 .

inorder to arrive at such equation , search your array for multiple of 3 ..
in our case they are {3,6,9,12,15} = {3x1 , 3x2 ,3x3 , 3x4 , 3x5 }
search for its corresponding multiples of 4 { 4x1 , 4x2 , 4x3 , 4x4 , 4x5 }
we will be able to find { 4,8,12}
repeat the same for 5 .. if {5,10,15 } exists as for my above case , then such equations exist and can be printed accordingly .

Two things struck me, a^2+b^2=c^2 is in terms of Pythagoras theorem for a triangle. Another important property of triangle is sum of any two sides is always greater than the third side. Put the two together on a sorted array.

SA()
		for each i fro 0 to n-1
			a[i] =  a[i]*a[i]
			
	PT()
		for each i from 0 to n-3
			j = i+1
			k = n-1
			a = s[i]
			while(j<k)
				b = s[j]
				c = s[k]
				if(a+b-c < 0)
					k = k-1
				if(a+b-c > 0)
					j = j+1
				else
					print sqrt(a),sqrt(b) and sqrt(c)
					break
	
	main()
		SA()
		PT()

public static void main(String[] args) {
int[] a = {1, 2, 3, 6, 7, 8, 9, 10};
boolean temp = false;

for (int i = 0 ; i < a.length ; i++){
temp = triangle(a, 0, i, a.length - 1);
if (temp == true)
break;
}
System.out.println(temp);
}

public static boolean triangle (int[] setNum, int start, int mid, int end){

if (start == end)
return false;

if ( Math.pow(setNum[start], 2) + Math.pow(setNum[end], 2) == Math.pow(setNum[mid], 2))
return true;

else if ( Math.pow(setNum[start], 2) + Math.pow(setNum[end], 2) > Math.pow(setNum[mid], 2))
return triangle (setNum, start, mid, end - 1);

else if ( Math.pow(setNum[start], 2) + Math.pow(setNum[end], 2) < Math.pow(setNum[mid], 2))
return triangle (setNum, start + 1, mid, end);
else
return false;
}

If there can be float in the array... best possibility is o(n^2) as far as I know...
If it natural numbers only, there a lot of optimization possible...
could have a function giving o(n^1.5) or even better...
As everyone said... save all the possible answer...

bool fQuestion(int arr[],int arrLength)
{
obj hash = new hashtable();

//load the square of all values in the hash o(n)
for(int i=0;i<arrLength;i++)
hash.add(arr[i]^2);

//using an o(n^2) method
for(int i=0;i<arrLength;i++)
for(int j=i+1;j<arrLength;j++)
if(hash.exist(arr[i]^2+arr[j]^2)) return true;
return false;
}

If you did for(int j=0;j<arrLength;j++)
Basically checking some value twice in the 2nd loop...
I would also ask you to optimize your algorithm, just saying maybe
he just wanted you to optimize your code and not the degree

If the array contain only natural number, it can be optimized exponentially...
First save all natural values a,b,c
for(int i=1;i<maxValue;i++)
for(int j=i;j<maxValue;j++)
if(isNaturalNumber(sqrt(i^2+j^2))) {
// for value sqrt(i^2+j^2) save the possibility i, j
}
Now for any number in the array, check if all of it possibilities exist in the array.
Lots of numbers doesn't even have number such as a^2+b^2=c^2
Due to the low amount of possibilities better to just have a list of valid answer.
But I wouldn't code such a thing, i would just explain it.

if max value is 10, you only have 2 possibility (5=>(3,4) and 10=>(6,8)
so knowing the amount of valid values is low...
Just make a database of all values up to a few millions, and you will be able to make an o(n)
Just parse it once, and check if there any possible values if that value is c

Just saying, the amount of possibility is too low...
Amazon... question... maybe he was aiming for the 2nd answer...
Make a database of all possible answer... who knows...

Use a^2+b^2 = (a+b)^2-2ab :)

How do I do the same problem using python??