Suppose to have an array of k bits. At step 1 all the bits are set to 1, at step 2 all the even bits change their state, at step 3 all the bits which are multiple of 3 change their state, at step k all the bits which are a multiple of k change their state. How many bits will be set to 1 at step k?
There is a simple quadratic algorithm, but it turns out that there is a closed formula to compute the number of bits set to 1 at step k.
hint: you can prove that the k-th bit is inverted a number of times equal to the factors of i. Therefore you need to find those numbers which have an odd amounts of factors. You can prove that these numbers must be a perfect square.
ReplyDeleteThe final problem is to estimate how many perfect square numbers there are before k. This is floor(sqrt(k)).