JavaScriptで数値内の連続するn桁の最大積を求める方法

2つの数値を第1引数と第2引数として受け取るJavaScript関数を作成します。ここでは、これらをそれぞれ m と n と呼ぶことにします。

1つ目の数値 m は一般に複数桁の数値であり、2つ目の数値 n は常に m の桁数より小さい値であるとします。

この関数は、m の中から連続する n 個の桁を取り出したとき、その積が最大になるグループを見つけ出す必要があります。

例

入力が以下の場合について考えてみましょう。

const m = 65467586;
const n = 3;

このときの出力は次のようになります。

const output = 280;

理由は、7 × 5 × 8 = 280 となり、この数値の中で連続する3桁の積として最大だからです。

解決アプローチ：スライディングウィンドウ

最も単純な方法は、すべての連続する n 桁の組み合わせに対して積を毎回計算することですが、より効率的なのが「スライディングウィンドウ」の考え方です。最初の n 桁の積を求めた後、ウィンドウを1桁ずつずらしながら、抜けていく桁で割り、新しく入ってくる桁を掛けることで、新しい積を定数時間で更新できます。これにより、全体の計算量は数値の桁数に比例する程度に抑えられます。

コード例

以下が実際のコードです。

const m = 65467586;
const n = 3;
const largestProductOfContinuousDigits = (m, n) => {
   const str = String(m);
   if(n > str.length){
      return 0;
   };
   let max = -Infinity;
   let temp = 1;
   for(let i = 0; i < n; i++){
      temp *= +(str[i]);
   };
   max = temp;
   for(let i = 0; i < str.length - n; i++){
      temp = (temp / (+str[i])) * (+str[i + n]);
      max = Math.max(temp, max);
   };
   return max;
}
console.log(largestProductOfContinuousDigits(m, n));

出力結果

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

280

注意点：0が含まれる場合

上記の実装は除算を利用しているため、数値の中に「0」が含まれていると、0による除算が発生して NaN が返されてしまう可能性があります。0 を含む入力にも対応したい場合は、各ウィンドウごとに積を素直に再計算する次のような実装が安全です。

const largestProductSafe = (m, n) => {
   const str = String(m);
   if(n > str.length) return 0;
   let max = 0;
   for(let i = 0; i <= str.length - n; i++){
      let product = 1;
      for(let j = i; j < i + n; j++){
         product *= +str[j];
      }
      max = Math.max(max, product);
   }
   return max;
};

この方法は計算量がやや増えますが（O(桁数 × n)）、どのような入力に対しても正確な結果を得られるという利点があります。用途に応じて、速度重視ならスライディングウィンドウ方式、堅牢性重視なら再計算方式を選択するとよいでしょう。