“Distributing <=K things, to N people, is same as distributing exactly K things, to (N+1) people”.
Why is this so? Can you let know the analysis?
Your solution is O(N) which is bad.
^ As he said, the extra person is a dummy. That is to say, the first n people will get some c (say) <= k things, the remaining (k - c) will go to the last person. There will be a case where the last guy gets everything, so we do -1 to get the right answer.
4 Likes
c might get negative and c%MOD will still be negative.
if you do (c+MOD)%MOD, it’ll give positive.
Thank you… Didn’t thought about this case. In whole contest , I was busy in optimizing my code.
lol 
I was doing tge same mistake earlier. But then i realised it for good
Your solution is O(N). It should get TLE for the last subtask.
You don’t use Lucas’ theorem. O(N) is not optimal
I am getting SIGSEGV in the last sub-task. I have used lucas theorem, still. Not sure what’s going wrong. Can anyone help?
Here’s the code -