Here is an interesting puzzle a friend/colleague put me to a few days ago:

You are given a very (very, very ….you get how very, don’t you?) long array of natural numbers and another natural number k. The task is to find out if there is any the first sequence of numbers in the array whose sum is divisible by k (if there is any). Of course, you need to come up with the most efficient algorithm for this.

Useless hint: This can be accomplished in O(n), n being the size of the array. Update: I’m not sure if my solution is correct, so I’m not even sure if this (useless) hint is correct.