Minimum removals in a number to be divisible by 10K

Given two positive integers N and K. Find the minimum number of digits that can be removed from the number N such that after removals the number is divisible by 10^K or print -1 if it is impossible.

Examples:

Input : N = 10904025, K = 2
Output : 3
Explanation : We can remove the digits 4, 2 and 5 such that the number 
becomes 10900 which is divisible by 102.

Input : N = 1000, K = 5
Output : 3
Explanation : We can remove the digits 1 and any two zeroes such that the
number becomes 0 which is divisible by 105

Input : N = 23985, K = 2
Output : -1

Approach : The idea is to start traversing the number from the last digit while keeping a counter. If the current digit is not zero, increment the counter variable, otherwise decrement variable K. When K becomes zero, return counter as answer. After traversing the whole number, check if the current value of K is zero or not. If it is zero, return counter as answer, otherwise return answer as number of digits in N – 1, since we need to reduce the whole number to a single zero which is divisible by any number. Also, if the given number does not contain any zero, return -1 as answer.

Below is the implementation of above approach.

C++ program for Minimum removals in a number to be divisible by 10^K

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

int countDigitsToBeRemoved(int N, int K)
{
    string s = to_string(N);
    int res = 0;
    int f_zero = 0;

    for (int i = s.size() - 1; i >= 0; i--) {
        if (K == 0)
            return res;
        if (s[i] == '0') {
            f_zero = 1;
            K--;
        }
        else
            res++;
    }
    if (!K)
        return res;
    else if (f_zero)
        return s.size() - 1;

    return -1;
}

int main()
{
    int N = 10904025, K = 2;
    cout << countDigitsToBeRemoved(N, K) << endl;

    N = 1000, K = 5;
    cout << countDigitsToBeRemoved(N, K) << endl;

    N = 23985, K = 2;
    cout << countDigitsToBeRemoved(N, K) << endl;

    return 0;
}

Time Complexity :Number of digits in the given number.