[解決済み] 簡単な面接問題が難しくなった：1～100の数字が与えられたとき、ちょうどk個の数字が欠けていることを見つけなさい。

質問内容

以前、面白い面接を経験したことがあります。質問はとても簡単なものでした。

Q1 : 数字が入った袋があります 1 , 2 , 3 , ..., 100 . 各数字はちょうど1回ずつ現れるから、100個の数字がある。ここで、袋の中からランダムに1つの数字が選ばれます。足りない数字を見つけなさい．

もちろん、この質問は以前にも聞いたことがあるので、すぐにこう答えました。

A1 : まあ、数字の合計が 1 + 2 + 3 + … + N は (N+1)(N/2) (参照 ウィキペディア：算術級数の和 ). については N = 100 の場合、その和は 5050 .

したがって、すべての数字がバッグの中に存在する場合、合計は正確には 5050 . 1個足りないので、和はこれより小さくなり、その差がその数です。そこで、その足りない数字を O(N) 時間と O(1) 空間

この時点ではうまくいったと思っていたのですが、突然、質問が思わぬ方向に進みました。

Q2 : その通りですが、では、次のような場合はどうするのでしょうか。 TWO の数字が欠けているのですか？

このバリエーションを見たことも聞いたことも考えたこともなかったので、パニックになってしまい、質問に答えられませんでした。面接官は私の思考プロセスを知りたがったので、予想される製品との比較でより多くの情報が得られるかもしれない、あるいは1回目のパスで情報を収集した後に2回目のパスを行うかもしれない、などと述べましたが、実際には解決への明確な道筋があるわけではなく、ただ闇雲に質問しているような状態でした。

面接官は、「2つ目の方程式があるのは、確かに問題解決の1つの方法だ」と励ましてくれたのですが。このとき、私は（事前に答えを知らなかったことに）ちょっと動揺して、これが一般的な（役に立つ）プログラミングのテクニックなのか、それとも単なるトリックやゴッチャの答えなのか、と質問しました。

面接官の答えに驚いたのは、このテクニックを一般化して、3つの欠番を見つけることができる、ということだ。実際、次のように一般化することができます。 k の数が足りない。

Qk : もし正確に k の数が足りない場合、どのようにすれば効率よく見つけることができるでしょうか？

これは数ヶ月前のことですが、このテクニックが何なのか、まだわかりませんでした。 明らかにあるのは Ω(N) すべての数字を少なくとも一度はスキャンしなければならないので、時間の下限はありますが、面接官が主張するのは 時間 と スペース 解決手法の複雑さ（マイナス O(N) 時間入力スキャン)で定義されます。 k ではなく N .

だから、ここでの疑問は単純だ。

• をどのように解決するのでしょうか？ Q2 ?
• どのように解決しますか？ Q3 ?
• どのように解決しますか？ Qk ?

明確化

• 一般に、以下のようなものがあります。 N から1...までの数字 N 1～100だけではありません。
• 私は、明らかなセットベースのソリューション、たとえば ビットセット のように、各数字の有無を指定されたビットの値で符号化する。 O(N) ビットを追加で使用します。に比例したスペースを追加する余裕はありません。 N .
• また、明らかなソートファーストのアプローチも求めていない。これとセットベースのアプローチは、インタビューで言及する価値があります（実装が簡単で、かつ、依存するのは N 非常に実用的です）。私は、聖杯のような解決策（実用的であるかどうかはわからないが、それでも望ましい漸近特性を持つもの）を探している。

ですから、繰り返しになりますが、当然ながら、入力をスキャンして O(N) で定義される）わずかな情報しか取り込むことができません。 k ではなく N ) を見つけなければなりません。 k をどうにかして消してください。

どのように解決するのですか？

以下は、その概要です。 ディミトリス・アンドレウの リンク .

i=1,2,...,kのi番目の累乗の和を覚える。これにより、この問題は次の連立方程式を解くことになる。

a <サブ 1 + a <サブ 2 + ... + a <サブ k = b <サブ 1

a <サブ 1 ² + a <サブ 2 ² + ... + a <サブ k ² = b <サブ 2

...

a <サブ 1 ^k + a <サブ 2 ^k + ... + a <サブ k ^k = b <サブ k

使用方法 ニュートンのアイデンティティー を知ることで、b <サブ i を計算することができます。

c <サブ 1 = a <サブ 1 + a <サブ 2 + ... a <サブ k

c <サブ 2 = a <サブ 1 a <サブ 2 + a <サブ 1 a <サブ 3 + ... + a <サブ k-1 a <サブ k

...

c <サブ k = a <サブ 1 a <サブ 2 ... a <サブ k

多項式を展開すると、（x-a <サブ 1 )...(x-a <サブ k ) の係数は正確に c になります。 <サブ 1 , ..., c <サブ k - 見る ヴィエートの公式 . すべての多項式は一意的に因数分解するので（多項式環は ユークリッド領域 を意味します。 <サブ i は、並べ替えまでは一意に決まる。

これで、累乗を覚えていれば数字を復元できることの証明は終わりです。kが一定の場合は、この方法がよい。

しかし、kが変化する場合、直接の計算方法であるc <サブ 1 ,...,c <サブ k は法外なコストがかかる。 _k は、すべての欠損数の積、大きさn！/(n-k)！となります。これを克服するために の計算をZ <サブ q フィールド ここで、q は n <= q < 2n となる素数であり、以下の式で存在する。 ベルトランのポスチュート . また、多項式の因数分解は一意であるため、証明は変更する必要がない。また、有限体上の因数分解のアルゴリズムも必要で、例えば、以下のものがあります。 ベルカンプ または カントール・ツァッセンハウス .

定数kのハイレベルな疑似コード。

• 与えられた数値のi番目の累乗を計算する
• 未知数のi乗の和を得るために引き算をする。その和をbと呼ぶ。 <サブ i .
• ニュートンの恒等式を使って、bから係数を計算する。 <サブ i それらをcと呼ぶ。 <サブ i . 基本的には、c <サブ 1 = b <サブ 1 ; c <サブ 2 = (c <サブ 1 b <サブ 1 - b <サブ 2 )/2; 正確な式はウィキペディアを参照してください。
• 多項式 x を因数分解する。 ^k -c <サブ 1 x ^k-1 + ... + c <サブ k .
• 多項式の根は、必要な数a <サブ 1 , ..., a <サブ k .

kを変化させながら、ミラー・ラビンなどを用いて素数n <= q < 2nを求め、qを減じた数すべてについて手順を実行します。

EDIT: この回答の以前のバージョンでは、Zの代わりに <サブ q ここで、qは素数であるため、標数2の有限体（q=2^(log n)）を使用することが可能です。ニュートンの公式はkまでの数による除算を要求しているので、この限りではありません。