配列の要素の積の最初の桁を求めるC++プログラム

はじめに

この記事では、与えられた配列のすべての要素を掛け合わせた積の、最初の桁（最上位の桁）を求めるプログラムについて解説します。

例として、次のような配列が与えられたとします。

arr = {12, 5, 16}

これらの要素の積は、12 × 5 × 16 = 960 となります。したがって、求める結果、つまり積の最初の桁は「9」になります。

アルゴリズム

1. 変数 prod を 1 で初期化する
2. ループを使い、配列の各要素を順番に prod に掛けていく
3. prod が 10 以上である間、prod を 10 で割り続ける
4. 残った一桁の値が、積の最初の桁となる

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int calc_1digit(int arr[], int x) {
    long long int prod = 1;
    for(int i = 0;i < x; i++) {
        prod = prod*arr[i];
    }
    while (prod >= 10)
        prod = prod / 10;
    return prod;
}
int main() {
    int arr[]={12,43,32,54};
    cout <<"The first digit will be: " << calc_1digit(arr,4)<< endl;
}

出力

The first digit will be: 8

コードの解説

calc_1digit 関数では、まず long long int 型の変数 prod を 1 で初期化し、for ループによって配列内の全要素を順に掛け合わせています。long long int を使うことで、通常の int 型では表現しきれない大きな積にもある程度対応できます。

その後の while ループでは、「任意の正の整数を 10 で割り続けると最終的に一桁になる」という性質を利用し、prod が 10 未満になるまで 10 で割る操作を繰り返すことで、積の最上位の桁だけを取り出しています。

計算量は、配列の要素数を n とすると掛け算の部分で O(n)、桁を削る部分で積の桁数分（O(log P)、P は積の値）かかるため、全体としては非常に効率的な処理です。なお、要素数が非常に多い場合や値が大きい場合はオーバーフローに注意が必要です。