इस समस्या में, हमें एक संख्या दी गई है और हमें संख्या से एक अंक हटाना है। ताकि हटाने के बाद बनी नई संख्या 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 में से किसी भी अंक को हटाया जा सकता है। यदि हटाने के लिए कई अंक उपलब्ध हैं तो हम उस अंक को हटाएंगे जिससे हटाने के बाद बनी संख्या सबसे बड़ी हो।
इनके आधार पर आइए कुछ समस्याओं को हल करते हैं और वांछित आउटपुट ढूंढते हैं -
जब अंतिम अंक विषम हो
1. 34241341
इस मामले में, हटाया जा सकने वाला एकमात्र अंक अंतिम स्थिति से 1 है और बनी संख्या 3432134 होगी जो 6 से विभाज्य है। तो, हम हटाए गए 1 की स्थिति लौटाएंगे यानी 8
2. 3214241
इस मामले में, हटाया जा सकने वाला एकमात्र अंक अंतिम स्थिति से 1 है और बनी संख्या 341224 होगी। जो 6 से विभाज्य नहीं है। तो, हम -1 लौटाएंगे।
जब अंतिम अंक सम हो
1. 8097860
इस मामले में, हमें संख्या को 3 से विभाजित करके शेषफल ढूंढना होगा जो 2 के बराबर है। तो, 2 शेषफल के मामले में, हम संख्या से 2, 5, 8 हटा सकते हैं। तो, स्थिति 1 से 8 और 5 हटाया जा सकता है ताकि संख्या 2 से विभाज्य बने। हम 5वीं स्थिति से 8 हटाएंगे क्योंकि यदि हम इसे पहली स्थिति से हटाते हैं तो एक छोटी संख्या लौटाई जाएगी। बनी नई संख्या 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
