Хитрая головоломка с интервью

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

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

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

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

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

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