C++で合計が0になるN個の一意な整数の配列を生成する方法

問題概要

整数 n が与えられたとき、合計が 0 になる n 個の「一意な(重複しない)整数」を含む配列を返すことを考えます。たとえば、入力が n = 5 の場合、[-7, -1, 1, 3, 4] のような配列が有効な答えのひとつになります。

解法のアプローチ

この問題は、非常にシンプルな発想で解くことができます。1 から n-1 までの整数を順に配列に格納しながら、それらの合計を記録しておきます。最後に、その合計の符号を反転した値を配列の末尾に追加すれば、配列全体の合計は必ず 0 になります。

具体的な手順は以下の通りです。

• 答えとなる配列 A を用意し、変数 x を 0 で初期化します。
• i を 0 から n-2 までの範囲でループします。
  • A[i] = (i + 1) とします。
  • x := x + i + 1 で合計を更新します。
• A[n-1] = -x とし、合計の符号を反転した値を格納します。
• 配列 A を返します。

この方法では、最初の n-1 個の要素はすべて正の異なる整数(1, 2, ..., n-1)であるため重複が発生せず、最後の要素 -x がそれらの合計をちょうど打ち消すため、条件を満たす配列が必ず得られます。計算量は O(n) と非常に効率的です。

C++での実装例

以下に、実際のC++コードを示します。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
      vector<int> sumZero(int n) {
         vector <int> ans(n);
         int x = 0;
         for(int i = 0; i < n - 1; i++){
            ans[i] = (i + 1);
            x += (i + 1);
         }
         ans[n - 1] = -x;
         return ans;
      }
};
main(){
   Solution ob;
   print_vector(ob.sumZero(10)) ;
}

入力

10

出力

[1, 2, 3, 4, 5, 6, 7, 8, 9, -45]

この出力では、1 から 9 までの整数と、その合計 45 の符号を反転した -45 が含まれており、配列全体の合計が 0 になっていることが確認できます。