【C++】「数値+逆順(数値)=10^N−1」を満たすN桁の数の個数を求める方法

本記事では、指定された条件を満たすN桁の数値の個数を求めるプログラムについて解説します。

具体的には、整数Nが与えられたとき、次の条件を満たすN桁の数値がいくつ存在するかを求めます。

数値 + 逆順(数値) = 10^N − 1

例えばN = 4の場合、10⁴ − 1 = 9999となるため、「数値とその逆順の和が9999になるような4桁の数」がいくつあるかを数えることになります。

考え方

この問題にはシンプルな数学的な性質があります。

• Nが奇数の場合: 条件を満たす数値は1つも存在しないため、答えは0になります。
• Nが偶数の場合: 各桁のペア(先頭と末尾、2桁目と末尾から2番目…)の和が必ず9になる必要があります。そのため、自由に決められるのは上位N/2桁だけで、先頭の桁は1〜9の9通り、残りのN/2 − 1桁はそれぞれ0〜9の10通りから選べます。

つまり、Nが偶数のときの答えは9 × 10^{N/2 − 1}となります。例えばN = 4なら、9 × 10 = 90個です。

答えが非常に大きな値になる可能性があるため、ここでは結果を数値ではなく文字列として構築しています。

実装例

#include <bits/stdc++.h>
using namespace std;

// 条件を満たす数値の個数を文字列として返す
string count_num(int N){
    // Nが奇数なら条件を満たす数は存在しない
    if (N % 2 == 1)
        return "0";
    // 9 × 10^(N/2 - 1) を文字列で表現する
    string result = "9";
    for (int i = 1; i <= N / 2 - 1; i++)
        result += "0";
    return result;
}

int main(){
    int N = 4;
    cout << count_num(N);
    return 0;
}

出力

90

計算量

時間計算量: O(N)
空間計算量: O(N)

ループは最大でもN/2回しか実行されないため、Nが大きくなっても高速に動作します。