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)?

Not worth another answer, but to see why harmonic series has logarithmic growth, you can graph y = 1/x and y = 1/(x+1) and use a little calculus to show that the nth harmonic number is bounded on the bottom by ln n, and bounded on the top by ln (n + 1). — Dennis Meng, Aug 03 '12 at 17:41

Kendall Frey · Accepted Answer · 2012-08-03T01:04:53.183

17

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).

edited Aug 03 '12 at 01:04

answered Aug 03 '12 at 00:44

Kendall Frey

43,130
20
110
148

Might be good to explain how you get the answer for the bonus too. :) – Dennis Meng Aug 03 '12 at 00:54
@DennisMeng: I almost feel bad ripping off the other answer. – Kendall Frey Aug 03 '12 at 00:56
Fair enough, but it'd be good to add why harmonic series has logarithmic growth. (Plus you can credit the other answer) – Dennis Meng Aug 03 '12 at 01:01

score 9 · Answer 2 · answered Aug 03 '12 at 00:37

9

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)

answered Aug 03 '12 at 00:37

Evgeny

6,261
8
35
43

barak1412 · Answer 3 · 2012-08-04T10:32:21.640

All numbers with an integer square will be true, the others false.

Proof:

We shall see that only the numbers with odd numbers that divide them, will be true:

Denote number N > 0.

According to a sentence from algebra, there are k different prime numbers p1,p2,...pk and non-zero integers m1 m2,...,mk

such: N = p1^m1 * p2^m2 ... pk^mk.

Thus, the number of numbers that divide N =

(m1 + 1)(m2 + 1)...*(mk + 1). Thats from combinatorics.

This number is odd <=> for each 1 <= j <= k , mj + 1 is odd <=> for each 1<= j <= k, mj is even <=> exist n1,n2,...,nk non-zero elements such mj = 2nj for each 1 <= j <= k.

So we get:

N = p1^2n1 * p2^2n2 .. pk^2nk => N = (p1^n1 * p2^n2 ... pk^nk)^2, as we wanted.

This is a mathematical proof.

Tricky interview puzzle

3 Answers3