CareerCup

Hash the square of all elements.

Simply Use two loops to get all possible a^2 + b^2 combinations and check if c^2 is in hash. T

Time: O(n^2). Space: O(n)

We need to sort the array to be able to achieve O(n^2) performance.

void findTriplets(int *input, int size)
{
int a, b, c, i;

for (c = 0; c < size; c++)
{
int result = input[c] * input[c];
a = 0;
b = size - 1;
while (a <= b)
{
if ((input[a] * input[a]) + input[b] * input[b]) < result) /* a^2 + b^2 < c^2 */
a++;
else if (input[a] * input[a]) + input[b] * input[b]) > result) /* a^2 + b^2 > c^2 */
b--;
else
printf("triplet found: %d %d %d \n", input[a], input[b], input[c]);
}
}
}
}}}
Time: O(n^2) Space: O(1)

Since If we will square any negative number then it will become positive number. So we can change all negative number to +ve it will take O(n) time complexity. After that sort array which will take nlogn. Now in end hold first number and start iteration from i = 0 to i = n-1 and j =n-1 to j= 0 where i must be less than j. In this way we can find triplets.

Note :- It will give solution in O(n*n) time complexity and O(1) space complexity if interviewer is allowing you to change array other wise you can modify quick sort code and instead of sorting it on the basis of a[i] we can use abs(a[i]).

give solution better than n^2 log n

1) First square all the numbers.
2) Sort the Array
3) Store this array element in a Hashset.
4)Open a for loop , which loops from starting element of the array.
5) open another for loop, which loops from next to starting element of array.
6) Add these two elements and check whether the sum is present in HashSet, if true break else continue.
7) By using HastSet we can reduce the time complexity for searching the result.

Example: When n = 2, the triple produced is 5, 12, and 13. (This formula is actually the same as method I, substituting m with 2n + 1.)
check : en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples

More formally: given a positive integer n, the triple can be generated by the following two procedures: (see mcs.surrey.ac.uk/Personal/R.Knott/Pythag/pythag.html )

a = 2n+1, b = 2n(n+1), c = 2n(n+1)+1

Example: When n = 2, the triple produced is 5, 12, and 13. (This formula is actually the same as method I, substituting m with 2n + 1.)

Alternatively, one can generate triples from even integers using the following formulas. Given that m is a positive even number,

a = 2m, b = m^2-1, c = m^2+1

Example: When m = 4, the triple produced is 8, 15, and 17 (this formula is another specific case of method I, substituting n with 1).

for(int i=0;i<N;i++) aux[i] = a[i]*a[i]; // O(N) 

quick_sort(aux); // O(N*log(N)

for(int i=0;i<N;i++) for(int j=0;j<i;j++) 
 binary_search(aux[i]+aux[j], aux); //  O(N^2*log(N))

Time complexity N^2*log(N), no extra space

actually, we can achieve o(n*n) at least for time complexity and O(1) for space complexity without HASH. We first need to change the value to its square one with its original sign, for example, 3=>9, -3=>-9. Then sort them using the fast sort according to the absolute value of the element, abs(9)=9, abs(-9)=9 in nlogn time complexity. then we are going to find the triple, using A+B=C, A=abs(a), B=abs(b), C=abs(c), a,b,c is the element of the square value. For each fixed C value, we know can search the pair A+B =C in O(n) time, so overall we can have O(n*n) time complexity for the case. if we choose the in place quick sort algorithm, the space complexity is O(1).

To find the pythagorean triplet.

A^2 + B^2 = C^2
You can simplify both the equation for using two variables.

A = n^2 - m^2;
B = 2nm;
C = n^2 + m^2;
for all n> m.

Now in the for loop print (A,B,C) for every pair of numbers by using above function.

Time Complexity O(n) Space O(1);