【C++】指定した範囲内で一の位がkとなる数値の個数を数える方法

区間 [first, last] が与えられたとき、その範囲内に存在する「一の位（1桁目）が k である数値」の個数を求める問題を考えます。

最も基本的な解き方は、i = first から i = last まで順番に数値を調べていき、各数値 i の一の位を k と比較し、一致していればカウントを1つずつ増やすというものです。一の位は剰余演算（% 10）を使うことで簡単に取り出せます。

具体的な例で確認してみましょう。

入力例1

入力： first=8, last=40, k=8
出力： 一の位がkの数値の個数 → 4

説明：

8から40までの間で一の位が8の数値：
8, 18, 28, 38

入力例2

入力： first=100, last=200, k=9
出力： 一の位がkの数値の個数 → 10

説明：

100から200までの間で一の位が9の数値：
109, 119, 129, 139, 149, 159, 169, 179, 189, 199
合計：10個

プログラムのアプローチ

• 2つの整数 first と last を受け取り、範囲 [first, last] を定義します。
• 関数 getCount(int fst, int lst, int k) は範囲を表す変数と k を引数に取り、fst から lst の間で一の位が k と一致する数値の個数を返します。
• カウントの初期値を 0 に設定します。
• forループで i = fst から i = lst まで繰り返し、各 i に対して ldigit = i % 10 として一の位を求めます。
• ldigit == k が成り立てば、カウントをインクリメントします。
• 最後にカウントを結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int getCount(int fst,int lst,int k){
   int count=0;
   for(int i=fst;i<=lst;i++){
      int ldigit=i%10; // 一の位を取得
      if(ldigit==k) // 一致していればカウントを増やす
         { ++count; }
   }
   return count;
}
int main(){
   int first = 5, last = 30;
   int K=5;
   cout<<"範囲内で一の位がKの数値の個数："<<getCount(first, last, K);
   return 0;
}

出力

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

範囲内で一の位がKの数値の個数：3

計算量について

このアプローチでは、範囲内のすべての数値を1回ずつ調べるため、時間計算量は O(last − first + 1)、必要な補助記憶域は O(1) となります。範囲が非常に大きい場合は、一の位ごとの出現パターンを数学的に求めることで高速化することも可能ですが、単純な範囲であればこの線形探索の方法が最も分かりやすく実装も容易です。