the link to solution-> https://www.codechef.com/viewsolution/14509342
You are using too much memory.
In the question, N can be upto 10^9. So, an array of N (64-bit) integers would take 64 * N bits, which is equal to 7.45 Gb (almost). This is a lot of memory for a single program.
One thing to notice is that in the above question, we don’t need all the indices. So, a better way will be to use a map.
You can see my solution for reference.
1 Like
If you WANT to solve it using array, then its possible. You just need to make an observation that lesser value of N are more frequently used.
Meaning, assuming we have stored all ans for N upto 10^9, you may not use N=10^8 a lot, but you will be using N=2,10,100 etc. much more. Why? Because smaller values will come in handy when you get a LARGER number, which breaks down to use the N.
Just make some cases and a recursion tree, and see which values of N are getting repeated alot. Once you come to agree that smaller Ns are more important than larger N, then its simple.
Declare an array of size 10^7, and store the result if N<=10^7. You can afford multiple same recursions for values between 10^7-10^9, if you are able to answer smaller numbers in O(1) time via memonisation.
Also, in this process of division, greater the number, faster it decreases and lesser the recursion calls it takes. Smaller numbers take more time/calls .
For example, if we constantly divide by 2,
100/2=50 . Difference of 50.
10/2=5. Difference of only 5. 10 times slow than above example.