JavaScriptで配列の全要素を等しくするための最小操作回数を求める方法

問題の概要

数値 num を唯一の引数として受け取るJavaScript関数を作成する必要があります。この関数はまず、次のルールに基づいて n 個の要素からなる配列を構築します。

arr[i] = (2 * i) + 1;

たとえば、入力が 5 の場合、生成される配列は以下のようになります。

const arr = [1, 3, 5, 7, 9];

この関数の目的は、配列内のすべての要素を等しくするために必要な最小の操作回数を計算して返すことです。

「1ステップ」の定義

ここでいう1つの有効な操作とは、配列から異なる2つの数値を選び、片方に +1 を加算し、もう片方から -1 を減算することを指します。

上記の配列の場合、期待される出力は次のとおりです。

const output = 6;

解法の考え方

各操作では必ず +1 と -1 が同時に適用されるため、配列全体の合計値は常に一定に保たれます。したがって、最終的に全要素が到達すべき目標値は配列の平均値、すなわち num 自身となります。

そこで、num より小さい要素について「目標値との差分（不足分）」をすべて合計したものが、求める最小操作回数になります。配列は奇数のみで構成されており、その平均値も奇数であるため、各要素は必ず整数回の操作でぴったり目標値に到達できる点もポイントです。

実装コード

この問題のコード例は以下のとおりです。

const num = 5;
const minimumOperations = (num = 1) => {
   if(num === 1){
      return 0;
   };
   let arr = new Array(num);
   let i = 0;
   let res = 0;
   while(i < num){
      arr[i] = (2 * i) + 1;
      if(arr[i] < num) res += num-arr[i];
      i++;
   };
   return res;
};
console.log(minimumOperations(num));

出力結果

コンソールには以下のように表示されます。

6

この実装では、配列を一度走査するだけで答えが求まるため、時間計算量は O(n)、空間計算量も O(n) と非常に効率的です。入力が 1 の場合は配列の要素が1つだけなので、操作不要として即座に 0 を返しています。