Số chữ số xóa tối thiểu để số chia hết cho 10 mũ K trong C++

Đề bài

Cho hai số nguyên dương N và K. Tìm số chữ số tối thiểu có thể xóa từ số N sao cho sau khi xóa, số đó chia hết cho 10^K. In -1 nếu không thể.

Ví dụ

Nếu N = 10203027 và K = 2 thì phải xóa 3 chữ số. Nếu xóa 3, 2 và 7 thì số trở thành 10200 chia hết cho 10^2.

Thuật toán

1. Duyệt số từ cuối. Nếu chữ số hiện tại không phải 0, tăng biến đếm, ngược lại giảm biến K.
2. Nếu K bằng 0, trả về biến đếm làm đáp án.
3. Sau khi duyệt hết số, kiểm tra giá trị K hiện tại. Nếu bằng 0, trả về biến đếm; ngược lại trả về số chữ số của N - 1.
4. Nếu số cho trước không chứa chữ số 0 nào, trả về -1.

Ví dụ mã 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 << "Số lần xóa tối thiểu = " << getBitsToBeRemoved(n, k) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số lần xóa tối thiểu = 3