@All , The problm can be solved by Fast Fourier Transform . The Concept used here is to Convert the number in the array into a vector and Then apply multiplication using FFT . The below example will clear it .
I will start will finding Pair of all Number equal to every possible combination from a given set of numbers:- Take for example : Array Element :- 1 , 2 , 3 , 5 , 6 ---------------------------------------------------------- Combination Possible are :- Pair Sum ---- No of times 3 1 4 1 6 1 7 2 5 1 8 2 9 1 11 1 12 1 ------------------------------------ Represent it in the form of a polynomial to get -> f(x) = x + x^2 + x^3 + x^5 + x^6 Now calculate G(x)=f(x)*f(x) , rendering us the Polynomial as :- G(x) = x^2 + 2x^3 + 3x^4 + 2x^5 + 3x^6 + 4x^7 + 4x^8 + 2x^9 +2x^11 + x^10 + x^12 The number of the form in the above polynomial : = [A* X^N] ---> (int)(A/2) Give the number repeatation for the Pair Sum N . For example :- The Pair Sum 3 is the repeated floor(3/2) =1 times :- The Pair Sum 7 & 8 is the repeated floor(4/2) =2 times Similarly For getting the Value of Triplet Sum we need need to do multiplication on some polynomials (Done by FFT) . I liked this problm very much , it cost me much time , but I came to know abt the importance of FFT in Digital signalling . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.