हमें एक सरणी target[] दी गई है जिसमें संख्याएं हैं। हमें न्यूनतम चरण ढूंढने होंगे जिनमें सभी शून्यों वाली सरणी [0,0,0,0...] को निम्नलिखित दो ऑपरेशन का उपयोग करके target में बदला जा सके:
इंक्रीमेंट ऑपरेशन - सभी तत्वों को 1 से बढ़ाया जा सकता है, प्रत्येक इंक्रीमेंट ऑपरेशन को चरणों में व्यक्तिगत रूप से गिना जा सकता है। (n तत्वों में n इंक्रीमेंट के लिए चरण=n)
डबलिंग ऑपरेशन - पूरी सरणी को दोगुना किया जाता है। सभी तत्वों के लिए इसे एक बार गिना जाता है। (प्रत्येक डबलिंग ऑपरेशन सभी तत्वों के मान को दोगुना करता है, इसे चरणों में 1 के रूप में गिनें)
लक्ष्य लक्ष्य तक पहुंचने के लिए न्यूनतम चरणों की संख्या ढूंढना है। जैसे [0,0,0] [1,1,1] में न्यूनतम 3 चरणों में बन सकता है (सभी तत्वों पर इंक्रीमेंट ऑपरेशन द्वारा) और [2,2,2] एक और डबलिंग ऑपरेशन द्वारा बन सकता है, इस बार कुल 4 चरण (3 इंक्रीमेंट, 1 डबलिंग)।
इनपुट
target[]= { 1,2,2,3 } आउटपुट
{0,0,0,0} से लक्ष्य तक पहुंचने के लिए न्यूनतम चरण: 6 व्याख्या
प्रारंभ में हमारे पास { 0,0,0,0 } है
3 इंक्रीमेंट ऑपरेशन { 0,1,1,1 } //इंक्रीमेंट व्यक्तिगत रूप से होता है
1 डबलिंग ऑपरेशन { 0,2,2,2 } // डबलिंग सभी तत्वों पर होती है
2 इंक्रीमेंट ऑपरेशन { 1,2,2,3 }
कुल चरण= 3+1+2=6
इनपुट
target[]= { 3,3,3 } आउटपुट
{0,0,0} से लक्ष्य तक पहुंचने के लिए न्यूनतम चरण: 7 व्याख्या
प्रारंभ में हमारे पास { 0,0,0 } है
3 इंक्रीमेंट ऑपरेशन { 1,1,1 } //इंक्रीमेंट व्यक्तिगत रूप से होता है
3 इंक्रीमेंट ऑपरेशन { 3,3,3 }
कुल चरण= 3+1+3=7
प्रयुक्त दृष्टिकोण
- पूर्णांक सरणी target[] लक्ष्य तत्वों को संग्रहीत करती है जिन्हें पहुंचना है।
- फ़ंक्शन minSteps(int target[],int n) लक्ष्य सरणी और इसकी लंबाई 'n' को इनपुट के रूप में लेता है और सभी शून्यों से लक्ष्य तक पहुंचने के लिए न्यूनतम चरणों की संख्या लौटाता है।
- चर count का उपयोग चरण गणना संग्रहीत करने के लिए किया जाता है, प्रारंभ में 0।
- चर max का उपयोग उच्चतम तत्व संग्रहीत करने के लिए किया जाता है, प्रारंभ में target[0]।
- चर pos का उपयोग max के इंडेक्स को संग्रहीत करने के लिए किया जाता है, प्रारंभ में 0।
- यदि target[] सरणी में सभी शून्य हैं तो 0 लौटाएं क्योंकि किसी चरण की आवश्यकता नहीं है। (for (i=0;i
- अब इस दृष्टिकोण में हम target[] से सभी शून्यों तक पहुंचेंगे।
- विषम तत्वों से 1 घटाकर सभी तत्वों को सम बनाएं। प्रत्येक घटाव के लिए count बढ़ाएं (इंक्रीमेंट ऑपरेशन के समान)।
- अब हमारे पास सभी सम संख्याएं हैं।
- उसी लूप में अधिकतम मान और उसकी स्थिति भी ढूंढें और max और pos को आरंभ करें।
- अब हम पूरी सरणी को 2 से तब तक विभाजित करना शुरू करते हैं जब तक अधिकतम मान 1 न हो जाए। यदि कोई संख्या विषम हो जाती है, तो 1 घटाएं और count बढ़ाएं, पूरे विभाजन ऑपरेशन के लिए count एक बार बढ़ाएं।
- अंत में सभी तत्व या तो 0 या 1 होंगे, सभी 1 के लिए उन्हें 0 बनाएं और count फिर से बढ़ाएं।
- count में मौजूद चरणों को परिणाम के रूप में लौटाएं।
उदाहरण कोड
#include <bits/stdc++.h> using namespace std; int minSteps(int target[],int n){ int i; int count=0; int max=target[0]; int pos=0; for(i=0;i=max){ max=target[i]; pos=i; } } //2 से विभाजित करें जब तक सभी तत्व 1 न हो जाएं और count एक बार बढ़ाएं while(target[pos]!=1){ for(i=0;i आउटपुट
दिए गए वांछित सरणी को प्राप्त करने के लिए न्यूनतम चरण: 15
