C++で整数に含まれる「穴」の数を数える方法

0から9までの各数字に含まれる「穴」の数を格納した配列 holes[10] が与えられます。ここでいう「穴」とは、数字の字形にできる閉じた空間のことです。たとえば「0」「6」「9」には1個、「8」には2個の穴があります。本記事の目的は、入力として与えられた整数に含まれる穴の総数を求めることです。

各数字の穴の数は次のとおりで、holes[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 } として表されます。

• 0、4、6、9 → 1個
• 8 → 2個
• 1、2、3、5、7 → 0個

入力例1

number = 239143

出力例1

整数に含まれる穴の数: 2

説明

239143 の各桁の穴の数を足し合わせると
(0+0+1+0+1+0) = 2個
※ 9 と 4 にそれぞれ1個の穴があります

入力例2

number = 12345

出力例2

整数に含まれる穴の数: 1

説明

12345 の各桁の穴の数を足し合わせると
(0+0+0+1+0) = 1個
※ 4 に1個の穴があります

アプローチ

以下のプログラムで使用するアプローチは次のとおりです。

「number % 10」で最下位の桁(一番右の桁)を1桁取り出し、対応する holes[] の値をカウントに加算します。その後「number / 10」で数を1桁分小さくし、これを number が 0 になるまで繰り返します。

手順

• 整数を入力として受け取ります。
• holes[] 配列を初期化します。
• 関数 holes_integer(int number, int holes[]) は、整数に含まれる穴の数を返します。
• カウント count を 0 で初期化します。
• number > 0 の間、以下の処理を繰り返します。
• temp = number % 10 として最下位の桁を取り出し、holes[temp] を count に加算します。
• number を 10 で割り、桁を1つ減らします。
• 最後に count を結果として返します。

実装例(C++)

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

int holes_integer(int number, int holes[]){
    int count = 0;
    while (number > 0){
        int temp = number % 10;
        count = count + holes[temp];
        number = number / 10;
    }
    return count;
}

int main(){
    int number = 239143;
    int holes[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 };
    cout<<"整数に含まれる穴の数: "<<holes_integer(number, holes);
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

整数に含まれる穴の数: 2

計算量

このアルゴリズムの時間計算量は O(d) です(d は整数の桁数)。桁数は log10(数値) に比例するため、大きな数でも高速に処理できます。また、補助的に使用するメモリは O(1) と非常に効率的です。