C++でx^1〜x^nの各値に含まれる数字の出現頻度配列を作成する方法

問題の概要

2つの整数 x と n が与えられたとき、x¹, x², …, xⁿ の各値に出現する数字（0〜9）の頻度を格納した配列を作成することを考えます。

例えば、x = 15、n = 3 の場合を見てみましょう。x¹ から xⁿ までの値は以下のとおりです。

• 15¹ = 15
• 15² = 225
• 15³ = 3375

これらの値に含まれる各数字の出現回数を集計すると、結果は [0, 1, 2, 2, 0, 3, 0, 1, 0, 0] となります。この配列の各要素は、インデックス0〜9に対応する数字が何回出現したかを表しています。

解決の手順

この問題は、以下の手順で解くことができます。

• 0〜9の数字の出現回数を格納するための頻度カウント配列を用意し、すべて0で初期化します。

• x¹ から xⁿ までの各値について、桁を一つずつ取り出して調べ、対応するインデックスのカウントを1ずつ増やしていきます。

• 最後に、集計結果の配列を表示します。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;
void digitCount(double val, long arr[]) {
    while ((long)val > 0) {
        long digit = (long)val % 10;
        arr[(int)digit]++;
        val = (long)val / 10;
    }
}
void generateFreqArray(int x, int n) {
    long freq_count[10]={0};
    for (int i = 1; i <= n; i++){
        double val = pow((double)x, (double)i);
        digitCount(val, freq_count);
    }
    cout << "[";
    for (int i = 0; i <= 9; i++){
        cout << freq_count[i] << " ";
    }
    cout << "\b]";
}
int main() {
    int x = 15, n = 3;
    cout << "The frequency array is: ";
    generateFreqArray(x, n);
}

出力結果

The frequency array is: [0 1 2 2 0 3 0 1 0 0]

※ 出力メッセージは「頻度配列は次のとおりです」という意味です。

補足：実装上の注意点

pow() 関数は double 型を返すため、指数が大きくなると浮動小数点数の精度限界により誤差が生じる可能性があります。より大きな冪乗を正確に扱いたい場合は、unsigned long long 型による繰り返し乗算や、多倍長整数ライブラリの利用を検討するとよいでしょう。

また、このアルゴリズムの計算量は各冪乗値の桁数の総和に比例します。n が大きくなるほど桁数も急激に増加するため、実際に使用する際は扱う値の範囲に注意してください。