algorithm - トリッキーなインタビューパズル

Question

このコードは 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] が偶数回タッチされた場合は false になり、それ以外の場合は true になります。

問題は、これらの値がどのようなパターンを形成するかです。arr[15] が true か false かすぐにわかりますか? arr[81]はどうですか？

答えはわかっています (arr[x] は、x が整数の 2 乗の場合に true になります)。しかし、インタビュー中にどのようにすばやく答えを導き出せばよいのかわかりません。

おまけの質問は、N 個の配列要素に対して行うと仮定すると、このコードの時間計算量はどのくらいかということです (以下で回答します)。

score 17 · Accepted Answer

すべての完全な正方形アイテムは true になり、その他はすべて false になります。

これは、完全な正方形には奇数の一意の要素があるのに対し、他のすべての要素には偶数があるという事実によって説明されます。これは、完全平方の平方根が 1 つの因数としてカウントされるためです。

数値は、要素ごとに 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) 時間になります (他の回答でよりよく説明されています)。

score 9 · Accepted Answer

N 個の要素に対して実行すると、N + N/2 + N/3 + ... の操作が行われます。これは調和級数であり、級数の部分和は対数成長します。したがって、時間計算量は O(n*log n) です。

score 5 · Accepted Answer

整数の2乗の数値はすべて真になり、その他の数値は偽になります。

証拠：

それらを分割する奇数の数だけが真になることがわかります。

番号N>0を示します。

代数の文によると、k個の異なる素数p1、p2、...pkと非ゼロの整数m1m2、...、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、...、 1 <= j<=kごとにmj=2njなどの非ゼロ要素をnkします。

したがって、次のようになります。

N = p1 ^ 2n1 * p2 ^ 2n2 .. pk ^ 2nk => N =（p1 ^ n1 * p2 ^ n2 ... pk ^ nk）^ 2、必要に応じて。

これは数学的証明です。

3 に答える 3