Help with COINFLIP

Question Link is:-


Solution Link:-
https://www.codechef.com/viewsolution/28051999
In the Question Description it says Time Limit 5 sec and The value of n ranges to 10e9 which is a lot for O(n) solution i have optimised my solution a lot and thinks it should Pass the Test Case but it’s saying TLE. I want to know How??

g can be up to 20000, and you are looping N (which can be as big as 10^9) times for each g.

Edit:

To be a little more explicit, your solution is O(max_T \times max_g \times max_N) which is far too large; you can almost certainly do it in a much-more-reasonable O(max_T \times max_g)

Edit:

Ah - you’re also using (and leaking) huge amounts of RAM :slight_smile:

4 Likes

I will correct my Solution and make it in O(1) time but how am i using and leaking too much of RAM?

1 Like
char *arr=new char[n];

You’re allocating n bytes of RAM and never freeing it, and you’re doing this g times :slight_smile:

2 Likes