@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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
