ラッキー数字がk個以下の整数を数えるC++プログラムの解説

要素数nの配列Aと整数kが与えられた場面を考えてみましょう。「ラッキーナンバー」とは、10進表現において幸運な数字とされる「4」と「7」だけで構成される正の整数のことです。この記事では、配列Aに含まれる各整数のうち、ラッキー数字（4または7）の出現回数がk個以下であるものがいくつあるかを求める方法を解説します。

例えば、入力が A = [44, 74, 474, 154]、k = 2 の場合、出力は3になります。44はラッキー数字を2つ持ち、74も2つ持つため条件を満たします。一方、474はラッキー数字を3つ持つためk=2を超えており、対象外です。また、154はラッキー数字を1つしか含まないため、こちらも条件を満たします。

解法のアプローチ

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

1. 各要素について、下の桁から順に1桁ずつ確認していきます。
2. その桁が4または7であれば、カウンターcを1増やします。
3. 数値を10で割り、すべての桁の確認が終わるまで繰り返します。
4. 桁ごとの集計が完了した後、カウントcがk以下であれば答えfを1増やします。
5. すべての要素を処理し終えたら、fを結果として返します。

n := size of A
f := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   c := 0
   while A[i] is not equal to 0, do:
      if A[i] mod 10 is same as 4 or A[i] mod 10 is same as 7, then:
         (increase c by 1)
      A[i] := A[i] / 10
   if c <= k, then:
      (increase f by 1)
return f

実装例

理解を深めるために、実際のC++コードを見てみましょう。各数値を10で割りながら最下位の桁を取り出し、その桁が4か7かどうかを判定するシンプルな手法です。

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k){
   int n = A.size();
   int f = 0;
   for (int i = 0; i < n; ++i){
      int c = 0;
      while (A[i] != 0){
         if (A[i] % 10 == 4 || A[i] % 10 == 7)
            c++;
         A[i] /= 10;
      }
      if (c <= k)
         f++;
   }
   return f;
}
int main(){
   vector<int> A = {44, 74, 474, 154};
   int k = 2;
   cout << solve(A, k) << endl;
}

入力

{44, 74, 474, 154}, 2

出力

3