C++でnum + Rev(num) = 10^N − 1を満たすN桁の数の個数を求める方法

問題概要

整数Nが入力として与えられます。この記事の目的は、次の条件を満たすすべてのN桁の数の個数を求めることです。

num + rev(num) = 10^N − 1

つまり、あるN桁の数と、その数字を逆順に並べ替えた数との和が、9がN個並んだ数（999…9）と等しくなるような数がいくつ存在するのかを数えます。

入力例

N=4

出力

num + Rev(num) = 10^N − 1 を満たすN桁の数の個数 ― 90

説明

該当する数は以下の通りです ―

1. 1188 + 8811 = 9999
2. 2277 + 7722 = 9999
3. 1278 + 8721 = 9999
……合計90個

入力例

N=5

出力

num + Rev(num) = 10N − 1 を満たすN桁の数の個数 ― 0

説明

Nが奇数の場合、中央の桁は自分自身と足し合わされるため、その和が9になることはありません。したがって、条件を満たす数は存在せず、答えは0になります。

例：148 + 841 = 989

解法のアプローチ

任意のN桁の数について、その数と逆順の数との和が 10^N − 1（＝999…9、9がN個）になるのは、両者の対応する各桁のペアの和がすべて9になるときです。

• Nが奇数の場合：中央の桁は自分自身と足されるため、同じ数同士の和が9になることはありません。よって答えは0です。
• Nが偶数の場合：1桁目とN桁目、2桁目と(N−1)桁目、3桁目と(N−2)桁目…というように、対応する桁のペアの和がそれぞれ9である必要があります。可能なペアは (1+8)、(2+7)、(3+6)、(4+5)、(5+4)、(6+3)、(7+2)、(8+1)、(9+0) の9通りです。

したがって、答えは 9 × 10^{N/2 − 1} となります。

アルゴリズムの手順

• 整数Nを入力として受け取ります。
• 関数 digit_numbers(int N) は、num + Rev(num) = 10^N − 1 を満たすN桁の数の個数を返します。
• カウントの初期値を0に設定します。
• Nが奇数の場合（N % 2 == 1）、0を返します。
• それ以外の場合は、count = 9 * pow(10, N/2 − 1) を計算します。
• countを結果として返します。

C++コード例

#include <bits/stdc++.h>
using namespace std;
int digit_numbers(int N){
   int count = 0;
   if (N % 2 == 1){
      return 0;
   } else {
      count = 9 * pow(10, N/2 - 1);
   }
   return count;
}
int main(){
   int N = 4;
   cout<<"Count of all N digit numbers such that num + Rev(num) = 10^N - 1 are: "<<digit_numbers(N);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます ―

Count of all N digit numbers such that num + Rev(num) = 10^N - 1 are: 90