C++で先頭と末尾の桁が同じ数字になる数を数える方法

区間 [first, last] が与えられたとき、この範囲内で「先頭の桁」と「末尾の桁」が同じ数値がいくつ存在するかを求めるのが本記事の目的です。例えば 232 という数値は、先頭の桁も末尾の桁も 2 で一致しています。

この問題は、i = first から i = last まで順番に走査することで解決できます。各数値について先頭の桁と末尾の桁を比較し、両者が一致していればカウントを1つずつ増やしていきます。

それでは、具体的な例で確認してみましょう。

入力 − first = 8, last = 40

出力 − 先頭と末尾の桁が同じ数値の個数:5

説明 − 8 から 40 の間で先頭と末尾の桁が同じ数値は以下の通りです。

8, 9, 11, 22, 33

入力 − first = 100, last = 200

出力 − 先頭と末尾の桁が同じ数値の個数:10

説明 − 100 から 200 の間で先頭と末尾の桁が同じ数値は以下の通りです。

101, 111, 121, 131, 141, 151, 161, 171, 181, 191

プログラムで使用するアプローチ

• 2つの整数 first と last を受け取り、探索範囲 [first, last] を定義します。

• 関数 getFirstDigit(int num) は、渡された数値の先頭の桁を返します。

• num >= 10 の間、num を 10 で割り続けます。ループが終わった時点で num には先頭の桁のみが残っているため、その値を返します。例えば num = 232 なら、232 → 23 → 2 と変化し、先頭の桁である 2 が得られます。

• 関数 getCount(int fst, int lst) は範囲を受け取り、先頭と末尾の桁が一致する数値の個数を返します。

• カウントの初期値を 0 に設定します。

• for ループで i = fst から i = lst まで繰り返し、各 i に対して getFirstDigit(i) を呼び出して先頭の桁を fdigit に格納します(fdigit = getFirstDigit(i))。

• 末尾の桁は剰余演算を用いて ldigit = i % 10 として求めます。

• fdigit == ldigit であれば両者の桁は一致しているため、カウントを増やします。

• ループ完了後、カウントを結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 先頭の桁を求める
int getFirstDigit(int num){
   while (num >= 10)
      { num = num / 10; }
   return num;
}
int getCount(int fst,int lst){
   int count=0;
   for(int i=fst;i<=lst;i++){
      int fdigit=getFirstDigit(i);
      int ldigit=i%10; // 末尾の桁を取得
      if(fdigit==ldigit) // 両者が一致していればカウントを増やす
         { ++count; }
   }
   return count;
}
int main(){
   int first = 10, last = 23;
   cout<<"Numbers with same first and last digits:"<<getCount(first, last);
   return 0;
}

実行結果

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

Numbers with same first and last digits:2

計算量について

このアルゴリズムは区間内の各数値を一度ずつ調べるため、時間計算量は O(n × d) となります(n は区間の幅、d は各数値の桁数)。先頭の桁の取得は数値を 10 で割り続けるだけ、末尾の桁の取得は 10 で割った余りを求めるだけで実現できるため、非常にシンプルで効率的な実装となっています。