As with most of these sort of problems, the first thing to do is to forget writing a program to solve it completely. How would you solve it by hand? How would you explain to someone else how to solve it by hand?
You should work that out - and write it down - before you write a single line of code.
Once you understand how to solve it yourself you can write pseudo-code - the sequence of instructions that the computer will have to perform to solve it. And once you've got that you should find it much easier to convert that into code.
So, how would you solve it yourself?