棘手的面试难题

Question

你在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]？

我知道答案(当x是某个整数的平方时,arr [x]将是真的),但我不明白的是我应该如何在采访中快速提出它？

奖励问题是这段代码的时间复杂度,假设你为N个数组元素做了(我将在下面回答)？

Answer 1

所有完美的方形物品都是真的,其他都是假的.

这可以通过以下事实来解释:完美正方形具有奇数个独特因子,而所有其他因子具有偶数.这是因为完美正方形的平方根只算作一个因素.

对于每个因素,数字都会切换一次,例如:

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 ...切换,产生O(n log n)时间(在另一个答案中解释得更好).

Answer 2

如果你为N个元素执行,则会有N + N/2 + N/3 + ...操作.它是一个谐波系列,并且该系列的部分和具有对数增长.因此,时间复杂度为O(n*log n)

Answer 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,该数字是奇数<=>,对于每个1 <= j <= k,mj + 1是奇数<=>,mj是偶数<=>存在n1,n2,...,对于每个1 <= j <= k,nk非零元素,例如mj = 2nj.

所以我们得到:

N = p1 ^ 2n1*p2 ^ 2n2 .. pk ^ 2nk => N =(p1 ^ n1*p2 ^ n2 ... pk ^ nk)^ 2,如我们所愿.

这是一个数学证明.