आपको एक संख्या स्ट्रिंग के रूप में दी गई है। आपको यह ज्ञात करना है कि इसे 3 से विभाज्य बनाने के लिए कितने अंक हटाने की आवश्यकता है।
हम अधिकतम 2 अंक हटाकर एक संख्या को विभाज्य बनाते हैं। इसलिए, इसे 3 से विभाज्य बनाने के लिए हटाए जाने वाले अंकों की अधिकतम संख्या 2 है।
आइए कुछ उदाहरण देखते हैं।
इनपुट
92
आउटपुट
1
इसे 3 से विभाज्य बनाने के लिए हम 2 को हटा सकते हैं।
इनपुट
999
आउटपुट
0
दी गई संख्या स्वयं 3 से विभाज्य है।
एल्गोरिदम
- संख्या को स्ट्रिंग में आरंभ करें।
- संख्या का योग ज्ञात करें।
- यदि योग 3 से विभाज्य है, तो 0 वापस करें।
- यदि योग 3 से विभाज्य नहीं है और संख्या की लंबाई 1 है, तो हम इसे 3 से विभाज्य नहीं बना सकते। -1 वापस करें।
- संख्या पर पुनरावृति करें।
- संख्या से एक अंक हटाएं और विभाज्यता जांचें।
- यदि उपरोक्त शर्त पूरी होती है, तो 1 वापस करें।
- संख्या की लंबाई फिर से जांचें। यदि लंबाई 2 है, तो -1 वापस करें।
- अन्यथा 2 वापस करें।
कार्यान्वयन
निम्नलिखित C++ में उपरोक्त एल्गोरिदम का कार्यान्वयन है:
#include <bits/stdc++.h>
using namespace std;
int getNumSum(string n) {
int len = n.length(), sum = 0;
for (int i = 0; i < len; i++) {
sum += (int)n[i];
}
return sum;
}
int getDigitsCount(string num) {
int n = num.length();
int sum = getNumSum(num);
if (sum % 3 == 0) {
return 0;
}
if (n == 1) {
return -1;
}
for (int i = 0; i < n; i++) {
int currentDigit = num[i] - '0';
if (sum % 3 == currentDigit % 3) {
return 1;
}
}
if (n == 2) {
return -1;
}
return 2;
}
int main() {
string num = "7536836";
cout << getDigitsCount(num) << endl;
return 0;
}
आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्नलिखित परिणाम मिलेगा।
1
