【C++】配列の合計と積をゼロ以外にするための最小操作回数を求めるプログラム

問題概要

n個の要素からなる配列Aがあるとします。1回の操作では、配列Aの中から任意の1つの要素を選び、その値に1を加えることができます。このとき、配列内の全要素の合計と積の両方をゼロ以外の値にするには、最小で何回の操作が必要かを求めるのがこの問題です。

例として、入力が A = [-1, 0, 0, 1] の場合を考えてみましょう。初期状態では合計も積も 0 になっているため、出力は 2 となります。2番目と3番目の要素（いずれも 0）にそれぞれ1を加えて配列を [-1, 1, 1, 1] にすれば、合計は 2、積は -1 となり、どちらもゼロ以外の値になります。

解法の考え方

この問題は、次の2つの条件に着目することで効率的に解けます。

積がゼロにならない条件： 配列内に1つでも 0 が残っていると、積は必ず 0 になってしまいます。そのため、すべての 0 を少なくとも1回はインクリメントする必要があります。0の個数を cnt とすると、必要な操作回数は最低でも cnt 回です。

合計がゼロにならない条件： すべての 0 を 1 に変更した後の合計は「元の合計 ＋ cnt」となります。この値がまだ 0 である場合は、任意の要素に1を加える操作をもう1回追加するだけで合計をゼロ以外にできます。この時点で積はすでにゼロではないため、追加の操作によって積が再び 0 になる心配はありません。

アルゴリズムの手順

以下の手順に従って解きます。

sum := 0
cnt := 0
n := 配列Aのサイズ
i := 0 から i < n まで、i を1ずつ増やしながら繰り返し:
    x := A[i]
    sum := sum + x
    x が 0 の場合は cnt := cnt + 1
sum + cnt が 0 の場合は cnt + 1 を返し、それ以外は cnt を返す

C++での実装例

それでは、実際の実装を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   int sum = 0, cnt = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      int x = A[i];
      sum += x;
      cnt += x == 0 ? 1 : 0;
   }
   return sum + cnt == 0 ? cnt + 1 : cnt;
}
int main() {
   vector<int> A = { -1, 0, 0, 1 };
   cout << solve(A) << endl;
}

入力

{ -1, 0, 0, 1 }

出力

2

このアルゴリズムは配列を一度走査するだけで答えが求まり、計算量は O(n)。要素数が大きくなっても高速に動作する、とても効率的なアプローチです。