Хитрое собеседование

У вас есть этот код в Javascript (хотя выбор языка не имеет значения):

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

Очевидно, что после запуска этого кода в массиве будет множество значений true и false. Если arr [i] было затронуто ровно в несколько раз, оно будет ложным, иначе оно будет истинным.

Вопрос в том, какой шаблон формирует эти значения? Можете ли вы быстро сказать, будет ли arr [15] верным ложным? Как насчет arr [81]?

Я знаю ответ (arr [x] будет истинным, когда x - это квадрат некоторого целого числа), но я не понимаю, как я должен быстро его придумать во время интервью?

Вопрос о бонусе - это то, что является временной сложностью этого фрагмента кода, если вы сделаете это для элементов массива N (я отвечу на него ниже)?

Ответ 1

Все идеальные квадратные элементы будут истинными, все остальные ложные.

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

Это объясняется тем, что совершенные квадраты имеют нечетное число уникальных факторов, тогда как все остальные имеют четное число. Это связано с тем, что квадратный корень идеального квадрата считается единственным фактором.

Число переключается один раз для каждого его фактора, например:

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

Бонус: Алгоритм выполняет n + n/2 + n/3... toggles, что приводит к O (n log n) времени (объясняется лучше в другом ответе).

Ответ 2

Если вы сделаете это для N элементов, будут выполняться операции N + N/2 + N/3 +.... Это гармонический ряд, а частичные суммы ряда имеют логарифмический рост. Следовательно, временная сложность O (n * log n)

Ответ 3

Все числа с целым квадратом будут истинными, остальные - ложными.

Доказательство:

Мы увидим, что верны только числа с нечетными числами, которые делят их:

Обозначим число N > 0.

Согласно предложению из алгебры существует k различных простых чисел p1, p2,... pk и отличных от нуля целых чисел m1 m2,..., mk

такое: N = p1 ^ m1 * p2 ^ m2... pk ^ mk.

Таким образом, число чисел, которые делят N =

(m1 + 1) (m2 + 1)... * (mk + 1). То есть от комбинаторики.

Это число нечетно <= > для каждого 1 <= j <= k, mj + 1 нечетно <= > для каждого 1 <= j <= k, mj равно <= > существуют n1, n2,..., nk ненулевые элементы, такие mj = 2nj для каждого 1 <= j <= k.

Итак, получаем:

N = p1 ^ 2n1 * p2 ^ 2n2.. pk ^ 2nk = > N = (p1 ^ n1 * p2 ^ n2... pk ^ nk) ^ 2, как мы и хотели.

Это математическое доказательство.