JavaScriptで各要素が全要素の積になる配列を構築する方法

JavaScriptで「各要素が全要素の積」となる配列を構築する

数値の配列を受け取り、それをもとに新しい配列を構築するJavaScript関数を作成します。新しい配列の各要素には、その位置の要素自身を含む元の配列すべての要素の積が格納されます。

例

入力配列が次のとおりだった場合:

const arr = [1, 2, 3, 4, 5];

期待される出力は次のとおりです。

const output = [120, 60, 40, 30, 24];

これは、配列全体の積が 1 × 2 × 3 × 4 × 5 = 120 であるためです。各位置の値は「全体の積 ÷ その位置の要素」で求められます。たとえば先頭の要素なら 120 ÷ 1 = 120、2番目なら 120 ÷ 2 = 60 となり、これが [120, 60, 40, 30, 24] という結果に対応します。

解決のアプローチ

要件は「線形時間(O(n))かつ定数領域(出力用の配列を除く)」で処理することです。以下の手順で実現できます。

1. reduce() メソッドを使い、配列全体の積を一度だけ計算する(時間計算量 O(n))。
2. 各要素に対して、総積をその要素で割った値を結果配列に代入する(時間計算量 O(n))。

どちらのループも配列を一度ずつ走査するだけなので、合計の時間計算量は O(n) となり、追加で必要なメモリは結果配列のみです。

実装コード

const arr = [1, 2, 3, 4, 5];

const exclusiveProduct = (arr = []) => {
   // 配列全体の積を一度だけ計算:時間計算量 O(n)
   const product = arr.reduce((acc, val) => acc * val);

   const res = [];

   // 総積を各要素で割る:時間計算量 O(n)
   for (let i = 0; i < arr.length; i++) {
      res[i] = product / arr[i];
   }

   return res;
};

console.log(exclusiveProduct(arr));

実行結果

コンソールには次のように出力されます。

[120, 60, 40, 30, 24]

注意点:配列に 0 が含まれる場合

上記の実装は除算を利用しているため、配列に 0 が含まれると Infinity や NaN が発生し、正しい結果が得られません。そのようなケースにも対応したい場合は、「左からの累積積」と「右からの累積積」を組み合わせる手法が定番です。この方法なら除算を一切使わずに同じ結果を得られます。

const exclusiveProductSafe = (arr = []) => {
   const n = arr.length;
   const res = new Array(n).fill(1);

   // 左側の要素の累積積を適用
   let left = 1;
   for (let i = 0; i < n; i++) {
      res[i] *= left;
      left *= arr[i];
   }

   // 右側の要素の累積積を適用
   let right = 1;
   for (let i = n - 1; i >= 0; i--) {
      res[i] *= right;
      right *= arr[i];
   }

   return res;
};

console.log(exclusiveProductSafe([1, 2, 3, 4, 5])); // [120, 60, 40, 30, 24]
console.log(exclusiveProductSafe([1, 0, 3, 4]));     // [0, 12, 0, 0]

こちらも前後2回の走査だけで済むため、時間計算量は O(n) のままです。

入力に 0 が含まれないことが保証されているならシンプルな除算方式で十分ですが、不特定のデータを扱う場合は累積積方式のほうが堅牢です。用途に応じて使い分けるとよいでしょう。