CODEWITHSUNDEEP
algorithmmathtime-complexitycalculus
Evgeny
Evgeny

Reputation: 6290

Tricky interview puzzle

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

Upvotes: 11

Views: 2122

Answers (3)

barak1412
barak1412

Reputation: 1160

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.

Upvotes: 5

Kendall Frey
Kendall Frey

Reputation: 44316

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

Upvotes: 17

Evgeny
Evgeny

Reputation: 6290

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)

Upvotes: 9

Related Questions