@samm : for FFT method :- i dont find it working for sum of 3.
i.e f(x) * f(x) *f(x) , its not giving rite output. On Sat, Dec 17, 2011 at 9:56 PM, SAMMM <somnath.nit...@gmail.com> wrote: > @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. > > -- 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.
