# 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 10K 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 10K

```#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.