We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You could use Karatsuba algorithm instead of FFT for multiplication. It has worster complexity, but it is enough for this challenge.
Also it perfectly deals with mod arithmetics.
If anyone is able to find one, I'd be very interested in a Python solution that doesn't time out for testcases 6-11. I implemented the exact same algorithm in C++ and it worked immediately, and a quick look at the leaderboards shows a complete domination of C++ solutions, so I don't even know if a solution in Python even exists.
I spend week trying to find python implementation.
Translated C++ version worked at once.
Finally I did python implementation using numpy array routines. All other ways working with arrays in python were too slow.
(well, I guess the OP will not care anymore, but for everyone who is seeking the discussions for advice: )
You can make it with pure python, but you have to implement FFT for fast polynom multiplication (just did it. beware of precision issues!).
I think I'll try Karatsuba too, just to see if it's fast enough.
Note: I've avoided DFT and FFT up to this point, it has now taken me a few days to get it - if I can, it'll only take you half the time ;-)
seems my Karatsuba implementation is to slow by a factor of 2. However as it is completely unoptimized I guess that with a little effort the 100% are in reach here too.
No more comments
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
It's kinda weird that optimized brute force solutions could pass with ease, I didn't expect FFT to show up at the editorial at all.
In authors solution, he is using complex roots of unity.
How does he maintain precision while multiplying the complex numbers. I think in c++ we have complex numbers library support.
I am trying to implement it in JAVA. Can anybody help me
You could use Karatsuba algorithm instead of FFT for multiplication. It has worster complexity, but it is enough for this challenge. Also it perfectly deals with mod arithmetics.
Simple element by element multiplication works in 0.67s, 3 times faster than required.
I am not able to import Numpy in my python saolution please help me
If anyone is able to find one, I'd be very interested in a Python solution that doesn't time out for testcases 6-11. I implemented the exact same algorithm in C++ and it worked immediately, and a quick look at the leaderboards shows a complete domination of C++ solutions, so I don't even know if a solution in Python even exists.
I spend week trying to find python implementation. Translated C++ version worked at once. Finally I did python implementation using numpy array routines. All other ways working with arrays in python were too slow.
(well, I guess the OP will not care anymore, but for everyone who is seeking the discussions for advice: )
You can make it with pure python, but you have to implement FFT for fast polynom multiplication (just did it. beware of precision issues!).
I think I'll try Karatsuba too, just to see if it's fast enough.
Note: I've avoided DFT and FFT up to this point, it has now taken me a few days to get it - if I can, it'll only take you half the time ;-)
seems my Karatsuba implementation is to slow by a factor of 2. However as it is completely unoptimized I guess that with a little effort the 100% are in reach here too.