C++ में K तक बढ़ाई गई 10 घात से विभाज्य होने वाली किसी संख्या में न्यूनतम निष्कासन

समस्या कथन

दो धनात्मक पूर्णांक N और K दिए हुए हैं। अंकों की न्यूनतम संख्या ज्ञात कीजिए जिन्हें संख्या N से इस प्रकार हटाया जा सकता है कि निकालने के बाद संख्या 10K से विभाज्य हो। प्रिंट -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