C++でN以下の数値の中から桁の積の最大値を求める方法

問題概要

正の整数N（N > 0）が与えられたとき、N以下の数値の中で「各桁の数字の積」が最大となる値を求めるのがこの記事のテーマです。

例えば、N = 390の場合を考えてみましょう。389という数値の桁の積は 3 × 8 × 9 = 216 となり、これが390以下の数値の中で最大です。したがって、求める答えは216になります。

解法のポイント：再帰的アプローチ

この問題は、再帰呼び出しを使うことで簡潔に解くことができます。基本的な発想は、次の2つのパターンを比較するというものです。

• そのままの数値：Nの各桁を掛け合わせた積
• 繰り下がりを起こした数値：上位の桁を1減らし、最下位の桁を9に置き換えた場合の積

N = 390を例にとると、「390」をそのまま掛けると0が含まれるため積は0になってしまいます。そこで繰り下がりを考えると「389」が候補となり、積は216。こちらの方がはるかに大きいことが分かります。

アルゴリズムの手順

1. N = 0 の場合は 1 を返す（積の計算上の単位元として機能）。
2. N が 1 桁（N < 10）の場合は、N をそのまま返す。
3. それ以外の場合は、max(max_product(N / 10) × (N % 10), max_product(N / 10 − 1) × 9) を返す。

C++による実装例

#include<iostream>
using namespace std;

int max_product(int N) {
    if (N == 0)
        return 1;
    if (N < 10)
        return N;
    return max(max_product(N / 10) * (N % 10), max_product(N / 10 - 1) * 9);
}

int main() {
    int N = 432;
    cout << "Maximum product is: " << max_product(N);
    return 0;
}

実行結果

Maximum product is: 243

コードの解説

N = 432の場合、数値をそのまま掛け合わせると 4 × 3 × 2 = 24 ですが、再帰的な処理の中で「下位の桁を9に置き換えるパターン」も順番に評価されていきます。その結果、399（3 × 9 × 9 = 243）のような強力な候補が現れ、最大値は243となります。

このように、再帰によって各桁ごとに「そのまま使うか」「9に置き換えて繰り下がるか」を選択しながら探索することで、すべての有力な候補を漏れなく比較できます。計算量は入力値の桁数に比例するだけなので、非常に効率的な手法と言えます。