Counting Sheep (Google CodeJam 2016)

The first (and presumably easiest) of the four problems in the Qualification Round is a pretty straightforward counting problem:

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

What is the last number that she will name before falling asleep?

I'm sure there are a variety of ways to solve this, some more clever than others, but simply stepping through the entire process is sufficiently fast than we don't really need to worry about optimization.  (I should note that my goal as a new-ish, amateur programmer is simply to find a solution that works, not find one that will vault me to the top of the leaderboard.  I generally measure on the scale of minutes, not microseconds.)  My solution in Python is posted below.

The most interesting part of this problem is what to do about potentially non-terminating sequences.  For example, for N = 0, no amount of multiplication will ever reveal any of the digits from 1-9 and Bleatrix will never fall asleep!  So we need to account for that - are there other starting numbers for which this process will never end?

For my original solution, I somewhat arbitrarily assumed that if we hadn't found all ten digits after 1000 multiples of N had been examined, we never would.  This felt exceedingly sufficient but of course a proof would be nice, and the authors at Code Jam provided one after the contest closed.  They find that the sequence will terminate fairly quickly for any N, and in particular that the worst case (given the parameters of the problem) would take just 72 multiples.

So setting my limit at 1000 was an order of magnitude larger than it needed to be, but it still ran in just a fraction of a second and produced the correct output for both the small and large variants of the problem.  Not bad for my first-ever attempt at competitive programming!  Of course the problems got more difficult, as I'll write about in the next installments.

Leave a Reply