C++で配列要素の積の下位k桁を求める方法

n個の要素を持つ配列Aと数値kが与えられたとき、配列内のすべての要素の積の下位k桁を求める問題を考えてみましょう。

例えば、A = [15, 22, 13, 19, 17] の場合、各要素の積は 1385670 となります。ここで k = 3 とした場合、求めるべき下位3桁は「670」です。

解法のアプローチ

この問題を効率的に解くには、要素を掛け合わせる際に 10^k を法として剰余を取りながら計算します。

通常、配列の要素数が増えると積は急激に巨大化し、整数型のオーバーフローを引き起こす可能性があります。しかし、10^k で割った余りだけを保持すれば、積がどれほど大きくなっても、必要な下位k桁を正確に求められます。

これは数学的に妥当な手法です。なぜなら、積の下位k桁は「10^k で割った余り」そのものだからです。また、(a × b) mod m = ((a mod m) × (b mod m)) mod m という性質により、各段階で剰余を取っても最終結果は変わりません。

アルゴリズムの手順

1. mod = 10^k を計算します。
2. 最初の要素を mod で割った余りを初期値 mul とします。
3. 残りの各要素について、「要素を mod で割った余り」と mul を掛け合わせ、さらに mod で割った余りを mul に代入します。
4. ループ終了後の mul が求める下位k桁となります。

C++での実装例

#include<iostream>
#include<cmath>
using namespace std;

int displayLastKNumbers(int array[], int n, int k) {
    int mod = (int)pow(10, k);   // 10^k を計算
    int mul = array[0] % mod;     // 初期値を設定
    for (int i = 1; i < n; i++) {
        array[i] = array[i] % mod;
        mul = (array[i] * mul) % mod;  // 剰余を取りながら掛け合わせ
    }
    return mul;
}

int main() {
    int a[] = {15, 22, 13, 19, 17};
    int k = 3;
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Last K digits are: " << displayLastKNumbers(a, n, k);
}

出力結果

Last K digits are: 670

計算量の評価

• 時間計算量：O(n) — 配列の各要素を一度ずつ処理するだけです。
• 空間計算量：O(1) — 追加の記憶領域は定数個の変数のみで済みます。

このように、剰余演算を活用することで、大きな数値を扱わずに積の下位k桁をシンプルかつ高速に求めることができます。