Tricky interview puzzle

Question

You have this code in Javascript (even though language choice does not matter):

var arr = new Array(101);
for (skip = 1; skip <= 100; skip++) {
    for (i = 0; i <= 100; i+= skip) {
        arr[i] = !arr[i];
    }
}

Obviously, after this code is run, there will be bunch of true and false values in the array. If arr[i] was touched even number of times, it will be false, otherwise it will be true.

The question is what pattern do these value form? Can you quickly tell whether arr[15] will be true of false? What about arr[81]?

I know the answer (arr[x] will be true when x is a square of some integer number), but what I don't understand is how am I supposed to come up with it quickly during the interview?

The bonus question is what is time complexity of this piece of code, assuming you do it for N array elements (I will answer it below)?

Answer 1

All perfect square items will be true, all other false.

http://thedailywtf.com/Articles/Nerds,-Jocks,-and-Lockers.aspx

This is explained by the fact that perfect squares have an odd number of unique factors, whereas all others have an even number. This is because the square root of a perfect square counts as only one factor.

A number is toggled once for every factor it has, for example:

12 -> 1, 2, 3, 4, 6, 12 -> an even number, so still false
16 -> 1, 2, 4, 8, 16 -> an odd number, so true

Bonus: The algorithm performs n + n/2 + n/3 ... toggles resulting in O(n log n) time (explained better in the other answer).

Answer 2

If you do it for N elements, there will be N + N/2 + N/3 + ... operations. It is a harmonic series, and partial sums of the series have logarithmic growth. Therefore, time complexity is O(n*log n)