dhavaldevildave
BAN USERthis will work for 3,4,5 but not for 30,40,50 .. if u want to thn 40=b, so m , n = 5,4 (co prime) but u cant get 30 n 50. cuz we are multiplying with triplate a non square digit, now if 100 is multiplied then 300,400,500 .. so now if b=400 thn m,n = 50,40 though this are not co prime will give u this.... so my solution will work for all triplates who has no common divisiors :) n not for all :)
- dhavaldevildave August 19, 2012my answer exlanation (a^2 - b^2)^2 + (2ab)^2 = (a^2+b^2)^2 ... so if x=2ab thn thn u can have such... make example n try to under stand
- dhavaldevildave August 19, 2012According to en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple,
a = m^2 - n^2, b = 2mn, c = m^2 + n^2
so for all array element x=b find m and n (co-prime) n in O(1) using hash/or O(N log N) find a,c... thats it...
Proper Explanation :
Sort the array in O(N log N) time.
For each element b, find the prime factorization. Naively using a table of primes up to the square root of the largest input value M would take O(sqrt M/log M) time and space* per element.
For each pair (m,n), m > n, b = 2mn (skip odd b), search for m^2-n^2 and m^2+n^2 in the sorted array. O(log N) per pair, O(2^(Ω(M))) = O(log M)** pairs per element, O(N (log N) (log M)) total.
Final analysis: O( N ( (sqrt M/log M) + (log N * log M) ) ), N = array size, M = magnitude of values.
if we want to implement it in C thn how ??? n what would be time complexity, ??
- dhavaldevildave August 02, 2012
can we do like
- dhavaldevildave November 23, 20121) find slope of all two points
2) maximum number of slops which are same can be either parallel or in same line, so now finding equation and checking for those points only
this sol can give in less complexity
O(n^2M) where M=maximum number of same slope line segments