समस्या कथन
आकार n की एक सरणी दी गई है, कार्य सरणी के सभी तत्वों को 4 से विभाज्य बनाने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करना है। एक चरण को सरणी से किन्हीं दो तत्वों को हटाने और इन तत्वों का योग सरणी में जोड़ने के रूप में परिभाषित किया गया है
उदाहरण
यदि इनपुट सरणी {1, 2, 0, 2, 4, 3} है तो 3 ऑपरेशन आवश्यक हैं −
1 + 3 = 4 2 + 2 = 4 0 + 4 = 4
एल्गोरिदम
1. सरणी के सभी तत्वों का योग 4 से विभाज्य होना चाहिए। यदि नहीं, तो यह कार्य संभव नहीं है 2. मॉड्यूलस नामक आकार 4 की एक सरणी को 0 से आरंभ करें 3. एक काउंटर को 0 से आरंभ करें। यह किए गए चरणों की संख्या को ट्रैक करेगा 4. इनपुट सरणी को पार करें और प्रत्येक तत्व का मॉड्यूलस 4 लें 5. मॉड्यूलस सरणी में मॉड 4 मान के मान को 1 से बढ़ाएं 6. मॉड्यूलस[0] उन तत्वों की संख्या है जो पहले से ही 4 से विभाज्य हैं। इसलिए उन्हें किसी अन्य तत्व के साथ जोड़ने की आवश्यकता नहीं है 7. मॉड्यूलस[1] और मॉड्यूलस[3] तत्वों को संयुक्त करके 4 से विभाज्य संख्या प्राप्त की जा सकती है। इसलिए, दोनों के न्यूनतम मान तक काउंट बढ़ाएं 8. मॉड्यूलस[2] के प्रत्येक 2 तत्वों को संयुक्त करके 4 से विभाज्य तत्व प्राप्त किया जा सकता है। 9. शेष तत्वों के लिए, मॉड्यूलस[1] और मॉड्यूलस[3] का आधा मॉड्यूलस[2] में जोड़ें। 10. अब, काउंट को मॉड्यूलस[2] के आधे से बढ़ाएं। हम आधा लेते हैं क्योंकि हर दो तत्व एक के रूप में संयुक्त होते हैं 11. काउंट का अंतिम मान इनपुट सरणी के सभी तत्वों को 4 से विभाज्य बनाने के लिए आवश्यक चरणों की संख्या है
उदाहरण
#include <bits/stdc++.h> using namespace std; int getMinRequiredSteps(int arr[], int n) { int count = 0; int modulus[4] = {0}; int sum = 0; for (int i = 0; i < n; i++) { int mod = arr[i] % 4; sum += mod; modulus[mod]++; } if (sum % 4 != 0) { return -1; } else { if (modulus[1] > modulus[3]) { count += modulus[3]; } else { count += modulus[1]; } modulus[1] -= count; modulus[3] -= count; modulus[2] += modulus[1] / 2; modulus[2] += modulus[3] / 2; count += modulus[1] / 2; count += modulus[3] / 2; count += modulus[2] / 2; return count; } } int main() { int arr[] = {1, 2, 0, 2, 4, 3}; int n = sizeof(arr) / sizeof(arr[0]); cout << "न्यूनतम आवश्यक चरण = " << getMinRequiredSteps(arr, n) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
न्यूनतम आवश्यक चरण = 2