C++で10のK乗(10^K)で割り切れる数にするための最小削除桁数

問題文

正の整数 N と K が与えられます。N の桁をいくつか削除して、残った数が 10^K(10のK乗)で割り切れるようにしたいとき、削除が必要となる最小の桁数を求めてください。どのように削除しても条件を満たせない場合は -1 を出力します。

例

N = 10203027、K = 2 の場合を考えてみましょう。このとき必要な削除桁数は 3 桁です。「3」「2」「7」の 3 桁を取り除くと、数は 10200 となり、これは 10² = 100 で割り切れます。

アルゴリズム

まず押さえておきたいのは、「ある整数が 10^K で割り切れる ⟺ その数の末尾に 0 が K 個以上並んでいる」という性質です。したがって、数を一の位から順に走査し、0 以外の桁はすべて削除候補としてカウントし、0 を K 個見つけた時点で走査を打ち切るのが最適な戦略となります。

1. 数を末尾(一の位)から先頭へ向かって走査する。現在の桁が 0 でなければカウンターを +1、0 であれば変数 K を -1 する
2. 走査中に K が 0 になったら、その時点のカウンターの値を答えとして返す
3. 最後まで走査しても K が 0 にならない場合、0 が 1 つでも見つかっていれば「N の桁数 − 1」を答えとして返す
4. 数の中に 0 が 1 つも含まれていない場合は -1 を返す

C++ 実装例

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

int getBitsToBeRemoved(int n, int k) {
    string s = to_string(n);
    int result = 0;
    int zeroFound = 0;
    for (int i = s.size() - 1; i >= 0; --i) {
        if (k == 0) {
            return result;
        }
        if (s[i] == '0') {
            zeroFound = 1;
            --k;
        } else {
            ++result;
        }
    }
    if (!k) {
        return result;
    } else if (zeroFound) {
        return s.size() - 1;
    }
    return -1;
}

int main() {
    int n = 10203027;
    int k = 2;
    cout << "Minimum required removals = " <<
    getBitsToBeRemoved(n, k) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

出力

Minimum required removals = 3

コードのポイント

• to_string による文字列化: 整数 n を文字列に変換することで、各桁に簡単にアクセスできるようになります。
• 末尾からの走査: 一の位から順に確認することで、「末尾に K 個の 0 を残す」という条件を効率的に判定できます。
• 計算量: 数値の桁数を d とすると、時間計算量は O(d)、空間計算量も O(d)(文字列保持分)にとどまります。
• エッジケース: 0 が 1 つも含まれていない数(例：12345)に対しては、どのように削除しても 10^K の倍数を作れないため、-1 を返します。