Số xóa tối thiểu trong một số để chia hết cho 10 lũy thừa được nâng lên thành K trong C ++

Tuyên bố vấn đề

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

Ví dụ

Nếu N =10203027 và K =2 thì ta phải bỏ đi 3 chữ số. Nếu chúng ta loại bỏ 3, 2 và 7 thì số trở thành 10200 chia hết cho 102

Thuật toán

1. Start traversing number from end. If the current digit is not zero, increment the counter variable, otherwise decrement variable K
2. If K is zero, then return counter as answer
3. 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
4. If the given number does not contain any zero, return -1 as answer

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum required removals = 3