इस समस्या में हमें संख्या दी जाती है और हमें संख्या में से अधिक अंक निकालने होते हैं। ताकि हटाने के बाद बनने वाली नई संख्या 6 से विभाज्य हो।
आइए अवधारणा को बेहतर ढंग से सीखने के लिए एक उदाहरण लेते हैं -
Input : 1324 Output : 4
स्पष्टीकरण - चौथी संख्या को हटाने पर हमें 132 मिलेगा जो कि 6 से विभाज्य है।
यहां, हमें एक संख्या दी गई है और हमें उस स्थिति को वापस करना होगा जहां से संख्या को 6 से विभाज्य बनाने के लिए हटाया जाता है।
इस समस्या को हल करने के लिए, हम एक तर्क बनाने की कोशिश करेंगे जो समस्या को हल करता है। इसके लिए हम अपने ज्ञान का उपयोग करेंगे कि यदि कोई संख्या 2 और 3 से विभाज्य है तो वह 6 से विभाज्य है।
संख्या में से अंक हटाने के बाद बनी नई संख्या की 6 की विभाज्यता यानि 2 और 3 दोनों की विभाज्यता के लिए जाँच की जाएगी।
दृष्टिकोण
संख्या के आधार पर हम यह पता लगा सकते हैं कि किसी अंक को हटाकर बनाई गई संख्या 6 से विभाज्य होगी या नहीं। संख्या का अंतिम अंक देखने पर दो स्थितियाँ उत्पन्न होती हैं।
जब अंतिम अंक विषम हो
जब अंतिम अंक विषम हो तो अंतिम अंक को हटाना ही संभव है। और नई संख्या केवल 6 से विभाज्य नहीं होगी यदि अंतिम अंक के आगे का अंक सम हो। अन्यथा, समाधान संभव नहीं है।
जब अंतिम अंक सम हो
यदि अंतिम अंक सम है, तो संख्या को 3 से विभाजित करने पर हमें शेषफल ज्ञात करना होता है और इस संख्या के आधार पर हम जांच सकते हैं कि कौन सा अंक हटाया जा सकता है।
संख्या को 3 तीन मामलों से विभाजित करने पर -
शेष 1 है - यदि भाग का शेष भाग 1 है तो अंक 1, 4, 7 में से कोई भी अंक सरणी से हटाया जा सकता है। यदि हटाने के लिए कई अंक उपलब्ध हैं तो हम अंक को इस तरह से हटा देंगे कि हटाने के बाद बनने वाली संख्या सबसे बड़ी हो।
शेष 2 है - यदि भाग का शेष भाग 2 है तो अंक 2, 5, 8 में से कोई भी अंक सरणी से हटाया जा सकता है। यदि हटाने के लिए कई अंक उपलब्ध हैं तो हम अंक को इस तरह से हटा देंगे कि हटाने के बाद बनने वाली संख्या सबसे बड़ी हो।
शेष 3 है - यदि भाग का शेष भाग 1 है तो अंक 3, 6, 9 में से कोई भी अंक सरणी से हटाया जा सकता है। यदि हटाने के लिए कई अंक उपलब्ध हैं तो हम अंक को इस तरह से हटा देंगे कि हटाने के बाद बनने वाली संख्या सबसे बड़ी हो।
इनके आधार पर कुछ समस्याओं को हल करते हैं और वांछित आउटपुट प्राप्त करते हैं -
जब अंतिम अंक विषम हो
<एच3>1. 34241341इस स्थिति में, केवल एक अंक जिसे हटाया जा सकता है वह अंतिम स्थान से 1 है और बनने वाली संख्या 3432134 होगी जो कि 6 से विभाज्य है। इसलिए, हम हटाए गए 1 की स्थिति को वापस कर देंगे अर्थात 8
<एच3>2. 3214241इस मामले में, अंतिम स्थान से केवल 1 अंक हटाया जा सकता है और बनने वाली संख्या 341224 होगी। जो 6 से विभाज्य नहीं है, इसलिए, हम -1 को वापस करेंगे।
जब अंतिम अंक सम हो
<एच3>1. 8097860इस मामले में, हमें संख्या को 3 से विभाजित करने और शेषफल को खोजने की आवश्यकता है जो 2 के बराबर है। इसलिए, शेष के रूप में 2 के मामले में, हम संख्या से 2, 5, 8 को हटा सकते हैं। इसलिए, स्थिति 1 से 8 और संख्या को 2 से विभाज्य बनाने के लिए 5 को हटाया जा सकता है। हम 8 को 5वें स्थान से हटा देंगे क्योंकि यदि हम इसे पहले स्थान से हटाते हैं तो छोटी संख्या वापस आ जाएगी। बनने वाली नई संख्या 809760 होगी जो 6 से विभाज्य है तो, हम 5 वापस करेंगे।
उदाहरण
इस तर्क के आधार पर समस्या को हल करने के लिए एक प्रोग्राम बनाते हैं -
#include <bits/stdc++.h>
using namespace std;
void isDivisibleBy6(string num){
int n = num.length();
int a[n];
int sum = 0;
for (int i = 0; i < n; i++) {
a[i] = num[i] - '0';
sum += a[i];
}
if (a[n - 1] % 2){
if ( (a[n - 2] % 2 != 0) || (sum - a[n - 1]) % 3 != 0) {
cout << "-1" << endl;
}
else {
cout << n << endl;
}
}
else {
int re = sum % 3;
int del = -1;
int flag = 0;
for (int i = 0; i < n - 1; i++) {
if ((a[i]) % 3 == re) {
if (a[i + 1] > a[i]) {
del = i;
flag = 1;
break;
}
else {
del = i;
}
}
}
if (flag == 0) {
if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3)
del = n - 1;
}
if (del == -1)
cout << -1 << endl;
else {
cout << del + 1 << endl;
}
}
}
int main(){
string number = "343224152";
isDivisibleBy6(number);
return 0;
} आउटपुट
5