C++で範囲内の数値のうち、その数字とqをかけた積に共通する数字がないものを数える方法

この記事では、範囲を表す2つの整数 start と end、および整数 q が入力として与えられたとき、範囲内の数値のうち「その数値自身の数字と、qをかけた積の数字に共通する数字が1つも存在しない」ものの個数を求める方法を解説します。

例えば、数値が 5 で q が 3 の場合、積は 15 となります。5 と 15 はどちらも数字「5」を含むため、共通する数字があります。

一方、数値が 2 で q が 5 の場合、積は 10 となります。2 と 10 には共通する数字がないため、条件を満たします。

例で理解しよう

入力例1

start = 5, end = 10, q = 2

出力: 条件を満たす数値の個数は 5

説明: 条件を満たす数値は以下の通りです。

• 5（5 × 2 = 10）
• 6（6 × 2 = 12）
• 7（7 × 2 = 14）
• 8（8 × 2 = 16）
• 9（9 × 2 = 18）

10 は 10 × 2 = 20 となり、共通する数字「0」が存在するため除外されます。

入力例2

start = 20, end = 25, q = 5

出力: 条件を満たす数値の個数は 2

説明: 条件を満たす数値は以下の通りです。

• 22（22 × 5 = 110）
• 23（23 × 5 = 115）

アルゴリズムのアプローチ

このアプローチでは、start から end まで順に各数値を走査し、その数値と q をかけた積をそれぞれ文字列に変換します。次に、現在の数値の各文字の出現回数を記録する配列 arr[26] を作成します。その後、積の文字列を走査し、その文字に対応する arr[] の値がゼロでなければ共通する数字が存在するため 0 を返します。共通する数字がなければ 1 を返します。

手順は以下の通りです。

• 範囲変数と値 q を受け取ります。
• 関数 check(int i, int q) は、数値 i とその積 q×i の数字が共通しない場合に 1 を返します。
• to_string(i) を使って i を文字列 str に変換します。
• 積（temp = q × i）を to_string(temp) を使って文字列 str_2 に変換します。
• str の文字の出現回数を記録するため、頻度配列 arr[26] = { 0 } を用意します。
• for ループで str を走査し、arr[str[j] - '0']++ で頻度を更新します。
• for ループで str_2 を走査し、arr[str_2[j] - '0'] がゼロでない場合は共通する数字が存在するため 0 を返します。
• 共通する数字がなければ 1 を返します。
• 関数 unequal(int start, int end, int q) は、範囲変数と q を受け取り、条件を満たす数値の個数を返します。
• 初期カウントを 0 とします。
• for ループで i = start から i = end まで数値を走査します。
• check(i, q) を使って、数値 i とその積に共通する数字がないかを確認し、条件を満たせば count をインクリメントします。
• 最後に count を結果として返します。

実装例（C++）

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

int check(int i, int q) {
    string str = to_string(i);
    int length = str.size();
    int arr[26] = {
        0
    };

    int temp = i * q;
    string str_2 = to_string(temp);
    int length_2 = str_2.size();
    for (int j = 0; j < length; j++) {
        arr[str[j] - '0']++;
    }
    for (int j = 0; j < length_2; j++) {
        if (arr[str_2[j] - '0']) {
            return 0;
        }
    }
    return 1;
}

int unequal(int start, int end, int q) {
    int count = 0;

    for (int i = start; i <= end; i++) {
        if (check(i, q)) {
            count++;
        }
    }
    return count;
}
int main() {
    int start = 20, end = 40, q = 4;
    cout << "条件を満たす数値の個数: " << unequal(start, end, q);
    return 0;
}

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

出力

条件を満たす数値の個数: 1

計算量について

このアルゴリズムの時間計算量は O((end - start + 1) × d) です。ここで d は数値の桁数を表します。範囲内の各数値に対して、その数値と積の各桁を一度ずつ確認するためです。空間計算量は O(1) で、固定サイズの頻度配列のみを使用します。範囲が非常に大きい場合は、桁DP（digit DP）などのより高度な手法を検討する価値があります。