This is my solution c++ solution
So, I already know what’s the problem with my solution. for bigger values of N
Let’s say N = 1543483483434 and M = 39 my code is giving output-> -1.
because the formula I came up with is ((N*(N/2))+N/2) for even numbers.
so, as you can see this big number is getting multiplied by itself making the number super big. And the number becomes negative because of the cycle it goes through. Any suggestion? How can I fix this? Without using BigInteger!!
Thanks!!
In java you have the BigInteger class. You can use that. Or, you can code in Python as it automatically handles large numbers.
Thank you for the suggestion and I know bigInteger will work but using biginteger makes the code very complex, I seen people did this question by just using long that’s why I was wondering if I can solve this question without using BigInteger. I think I should’ve mentioned that!! sorry, my bad
There is a O(1) solution to this problem. Given that N*(N+1)/2=M, on expanding it gives you a quadratic equation. You can now find N in terms of M . We can prove that this N will be atmost ~{10}^{9}
Now you see if given N\ge {N_o} (N observed ,which we found by equation).
Alternatively - This question can be trivially solved via python. 
Hello @kunnu120,
You want to know the minimum number of shop visited so that the request M could be satisfied.
That means,find min N such as N*(N+1)/2 >= M , which is the same as N**(N+1) >= 2*M.
Also, N^2 < N(N+1) for N positive. So you can compute j = sqrt(2M) and start to check from j to n if j(j+1) >= 2*m. Normally, if such N exist, it will not big enough to overflow the long max value (it’s close to the square root of M, which max value is 10^18).
Find my solution here : https://www.codechef.com/viewsolution/14735718
Thank you for the explanation!!
Thank you for helping!!
so, Python integers don’t have any limit??
Python HAS a limit, but tis very large. If i remember, it was around 7000 digits. But well, such large numbers need more time in computation. You will probably get a TLE first.
Okay, thank you for the help
So, how do we know when there are not enough chocolates to get? what condition should it have to return -1 then?
AC!! how you came up with this equation?? Thanks
AC!! how you came up with this equation?? Thanks
Sorry for being unable to attend to your queries, I was kind of stuck/busy with something.
As I said, if the N required (which we found by equation) is more than given number of shops, then he cannot have enough chocolates.
The equation is nothing special. Its the sum of first N natural numbers, used as first shop has 1, 2nd has 2, third has 3…and so on (so total chocolates are 1+2+3… +N which is sum of N natural numbers). Hope this helps! 