【C++】Cで割り切れ、範囲[A, B]に含まれない最小の正の整数を求める方法

問題の概要

今回は興味深いプログラミング問題を取り上げます。3つの整数 A、B、C が与えられたとき、「X mod C = 0」を満たし、かつ X が範囲 [A, B] に含まれない最小の正の整数 X を求めることを考えます。

例えば、A = 5、B = 10、C = 4 の場合、答えとなる X の値は 4 です。これは、4 が C で割り切れ(4 ÷ 4 = 1)、かつ範囲 [5, 10] の外側に存在するためです。

解法のアプローチ

この問題は、以下のシンプルな手順で解くことができます。

• C が範囲 [A, B] に含まれない場合： C をそのまま結果として返します。C 自身が「C で割り切れ、範囲外にある」条件を満たす最小の値だからです。
• C が範囲 [A, B] に含まれる場合： B より大きい最初の C の倍数を求めて返します。具体的には、(B / C) × C + C という式で計算できます。

C++での実装例

#include <iostream>
using namespace std;

int findMinNumber(int a, int b, int c) {
    // Cが範囲[A, B]の外にある場合はCをそのまま返す
    if (c < a || c > b)
        return c;
    // Bより大きい最初のCの倍数を求める
    int res = ((b / c) * c) + c;
    return res;
}

int main() {
    int a = 2, b = 4, c = 2;
    cout << "Minimum number X: " << findMinNumber(a, b, c);
}

実行結果

Minimum number X: 6

この例では、A = 2、B = 4、C = 2 となっています。C = 2 は範囲 [2, 4] に含まれるため、B = 4 より大きい最初の 2 の倍数である 6 が出力されます。

計算量について

このアルゴリズムの時間計算量は O(1) です。比較と算術演算のみで構成されており、ループを使用しないため、入力のサイズに関わらず一定の速度で処理が完了します。空間計算量も O(1) であり、非常に効率的な解法といえます。