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.
Since value of the coefficients grow exponentially, after a few dozen of rows, even int64 wont be enough to store a single coefficient.
Hence if using modulo arithmetic (mod E9+7) through all the coefficient calculations is a valid solution, I see no way around it. So after a few rows no actual coefficient is evaluated only its modE9+7 modulo.
Now my problem is, that I must keep somehow track of the distinct (==not equal) coefficients. Tracking all the coefficients is undoable, (besides potentially being too many of them) since by using modulo arithmetic all the way long I can not get the actual coefficient only its mod (E9+7). Which may (or may not??) collide between to distinct coefficients whixh have the same modulo E9+7.
If I was sure that the modulo(E9+7) will not collide between two distict coefficients, a hash table with keys being the different modulo (E9+7) remainders and values being a bool would be an efficient way to keep track of uniquessness of squarefree numbers.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #203: Squarefree Binomial Coefficients
You are viewing a single comment's thread. Return to all comments →
Since value of the coefficients grow exponentially, after a few dozen of rows, even int64 wont be enough to store a single coefficient. Hence if using modulo arithmetic (mod E9+7) through all the coefficient calculations is a valid solution, I see no way around it. So after a few rows no actual coefficient is evaluated only its modE9+7 modulo.
Now my problem is, that I must keep somehow track of the distinct (==not equal) coefficients. Tracking all the coefficients is undoable, (besides potentially being too many of them) since by using modulo arithmetic all the way long I can not get the actual coefficient only its mod (E9+7). Which may (or may not??) collide between to distinct coefficients whixh have the same modulo E9+7.
If I was sure that the modulo(E9+7) will not collide between two distict coefficients, a hash table with keys being the different modulo (E9+7) remainders and values being a bool would be an efficient way to keep track of uniquessness of squarefree numbers.