C++でKに累乗された10の累乗で割り切れる数の最小削除

問題の説明

2つの正の整数NとKが与えられます。削除後に数が10Kで割り切れるような、数Nから削除できる最小桁数を見つけます。不可能な場合は-1を出力します。

例

N=10203027およびK=2の場合、3桁を削除する必要があります。 3、2、7を削除すると、数値は10200になり、102で割り切れる

アルゴリズム

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

例

#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