it’s just math

I recently became aware of Codility and it’s easy programming exercises.

Now I had fun with a few of them and they all shared a common trait: there was no programming skill involved if you knew the right math (usually undergraduate stuff every CS student should know).

To be honest: I find this kind of funny. Not long ago I red Why I’m not looking to hire computer science majors and then there are those sites that helps you find good programmers … by asking math questions lol

Personally I think you can be a great programmer without knowing any math but no matter what you will be a better programmer if you do.

So let’s have a look at one of those questions and how you can solve it in a few lines with simple (well…) math:

the problem

Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N − 1. You start to eat the chocolates. After eating a chocolate you leave only a wrapper. You begin with eating chocolate number 0. Then you omit the next M − 1 chocolates or wrappers on the circle, and eat the following one. More precisely, if you ate chocolate number X, then you will next eat the chocolate with number (X + M) modulo N (remainder of division). You stop eating when you encounter an empty wrapper. For example, given integers N = 10 and M = 4. You will eat the following chocolates: 0, 4, 8, 2, 6. The goal is to count the number of chocolates that you will eat, following the above rules.

Put it another way, the problem wants us to count the number of elements in the set

$$ C := \{ M \in \bf{Z}_N | 0, M, 2M, 3M, … \} $$

Maybe you should stop reading and try to solve this problem (without math) – the best thing I can think of quickly is to use something like a array of bools or hashset to mark the eaten chocolates … you get the idea.

There is an additional hint: it’s placed below Euclidean algorithm – so chances are high you have to use this algorithm.

Now if you try a bit you will find the solution rather quickly with just this hint, but you might not know why this is – if so: read on 😀

onwards to the math solution

The euclidean algorithm is used to compute the greatest common divisor of two numbers.

For positive integers the implementation in Fsharp is not difficult:

let rec gcd n m =
   if n < m then gcd m n else
   if m=0 then n else gcd m (n % m)

Now there is a small additional property of the GCD you need to know/remember: if \(d := gcd(n,m)\) then there exists numbers \(k,l\) such that \(d = kn + lm\) (this is not horrible hard to see: you just have write down the algorithm and go upwards – if you want a nice exercise you can try to write a implementation of the extended euclidean algorithm that gives you those factors back).

Now if you look carefully you should notice that if you take this equation mod n you end up with \(d = lm \ mod \ n\), which means that if you eat (add m) enough chocolates you end up by this d. And math tells us more: this d really generates \(C\) just like \(M\) did above.

Why? Well \(d\) is the smallest divisor of both \(M\) and \(N\) so of course it divides \(M\) and so you get back \(M\) if you add up enough \(d\). And as we have seen above you get back to \(d\) if you add up enough \(M\) – so both cyclic sets must be the same.

How does this help us?

Well \(d\) is a divisor of \(N\) too – so you end up by the zero-th chocolate after \( N/d \) steps if you start at \(d\) and there are no others as we just saw.

Yeah – we just found the answer:

let eatenChocolates n m =
    n / gcd n m

that’s all!

Now does this show you if you have a good programmer in front of you? Or if the candidate does not remember (or even know) this stuff does it show you that you don’t? No I guess – but still isn’t it cool that you can get blazing fast solutions in a matter of literally 5 lines of code where your first guess might have taken more lines and would have soon busted your patience and memory? Hell yes (or so I think)