Link to the problem
Can someone please explain how is the solution guaranteed to occur in k steps, otherwise the answer will be (-1). I am not able to understand how the remainders get repeated and why the solutions have looped till k, and if there is a rem as 0, answer exists otherwise not.
If someone can please explain in simple words it would be of much help. Also, if someone can provide a good resource for learning pigeonhole principle and how to apply it in problems, it would be a great help.
@galencolin @aneee004
Thanks in advance!
1 Like
Consider this. When you mod a number by K, the reminder is in the range 0 to K - 1.
Now as we loop through all the reminders, we have only two options:
- We see a reminder that was already seen
- We see something new.
If we see something old, we print -1 and return.
And we can see something new, only K times, as there are only K unique reminders.
2 Likes
Why to return if we see something that has already been seen 
This means, we will end up in an infinite loop and we will never find 0. If we have seen something already, and we see that again it means in between them 0 did not occur. And hence it will never occur.
Let’s say you saw 2 for the first time. Then 3 then 4 then 7. Now again 2. So after this you will see 3 again, because next reminder only depends on previous reminder.
So 2->3->4->7->2->3->4->7->2-> … \infty
3 Likes
Thanks for explaining with that example. I understood it 
2 Likes