配列の数値を集計する

Question

Nが負でない整数の配列を持ち、それぞれが非常に大きくなる可能性があるとします（0-> 100,000）。また、Nが非常に大きい（〜100,000,000）と仮定しましょう。

配列[a0 a1 ... aN-1]については、配列全体に対して（-2）^ aiの合計を返す関数を記述したいと思います。私はO（n * log（n））時間の複雑さとO（n）の空間を持っていたいと思います。

たとえば、（-2）^ 1 +（-2）^ 2 +（-2）^ 3 = -6を返します。 もう1つの制約は、100,000,000を超える回答、関数は-1を返します。

ナイーブ（間違った）溶液は、以下である：

int solve(vector<int> &A) { 
     int answer = 0; 
     for (auto iter = A.begin(); iter != A.end(); ++iter) { 
     answer += pow(-2, *iter); 
     } 
     return (answer <= 1e8) ? answer : -1; 
    } 

これはB/Cの答えが（ネイティブ符号付き整数のサイズは4バイトであると仮定して）> 31値のオーバーフローする働きません。 longを使用すると、配列の値が63より大きいb/cも機能しません。

高水準の解決策は、std :: sortを使用して配列をソートしてからそれを歩くことです。配列の値が31より大きい場合は、配列の値から31を引いて、31の倍数を除外します。これは、指数の合計を扱っている場合でも受け入れ可能です。この問題に対する既知の、O（n * log（n））の複雑さ、O（n）の空間解があるなら、私は興味がありました。

Answer 1

(-2)^Kには、偶数Kの場合は..00001000..、奇数K（2の補数）の場合は..1111110000..であることに注意してください。

したがって、合計を2進表現で累積するためにarray（intまたはboolean）を作成できます。長さは配列からの最大値（Nに依存するオーバーヘッド - Log2（N）個のセル）によって決定されるべきです。

次に、配列を歩き、現在の番号のバイナリ表現をアキュムレータに追加します。ソート入力アレイとグループ繰り返される値 - 配列A=[2,3,4]

value(K)  binary(-2)^K accum 
          00000000  
2   100   00000100 
3   11111000  11111100 
4   00010000  00001100 

ごとに動作を追加するための例は、Max（A）+ LOG2（N）の基本オペレーションを

可能ミニ最適化を要します。例えば、配列が8の値4を含む場合、7つの加算演算なしで、単一シフト演算で容易に8*(-2)^4= 10000 << 3 = 10000000を取ることができる。

1）「が100M

あなたはドンより低い項目の合計は何100M制限 2）に適合つながるん：

Answer 2

アイデア...

あなたの関数は、2つの質問に答えます1）が満たされない場合、後者を計算しなければならないので、最終的なカウントは、何かがintに適合するかどうかについてはあまり気にしない。

簡単にするために、カウントソートと合計カウントを使用できます。配列を2 ^（i）の乗数を保持するような数にすると、最終的な合計は合計（counts [i] * 2^i）になります。 個数は符号フリップフロップを使用していませんので、それを記入する際に適切な記号を付ける必要があります。

ここで、カウント配列を減らすことができます。カウントした場合は、[I]> 2、次いで合計は次のように変更アレイに対して同じであることに注意してください：

• カウント[I] -2
• カウント[I + 1] +1

負号にも同じことが適用されます。したがって、カウントの0から最大までの1つのループでは、カウントの値を減らして各値に0と1/-1しか残さないようにすることができます。

あなたが知っているように、2^Nインデックスの値は、少なくとも2回は0..2^N-2の値に累積されるものの合計よりも大きいです。だから、もしあなたの最高指数（減量後）が28（2^28 = 268,435,456）より大きければ、結果は100,000,000に収まらないでしょう。

1）が実行された場合、最終結果と一時的結果が268,435,456より大きくないので、int型に収まるので、数学を行い、最終結果を再度確認してください。