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.
One Response for "A CS Puzzle"
Umm.. looks more like a theory kosteen. Can I rephrase it like this?
Given an infinite sequence of numbers, can we guarantee that we can find sums of subsequences that map onto all possible values of k? The mapping is in terms of multiples of k or k itself, if the sum is prime.,
What I am thinking is, given an infinite sequence of numbers, start at a random location and go on computing the sums. Each sum will be a multiple of some ‘k’ or the other (or prime). So, it is possible to at least one subsequence whose sum is divisible by a given ‘k’.
I don’t know if this is valid at all. That aside, what is also not clear in your kosteen is: is it about being able to say that there is such a sequence or *finding* such a sequence (and then of course, saying that there is a sequence).
Leave a reply