सी ++ में दिए गए वांछित सरणी को प्राप्त करने के लिए न्यूनतम चरणों की गणना करें

हमें एक सरणी लक्ष्य [] दिया गया है जिसमें संख्याएँ हैं। हमें न्यूनतम चरणों का पता लगाना चाहिए जिसमें सभी शून्य [0,0,0,0…] के साथ सरणी को केवल निम्नलिखित दो ऑपरेशनों का उपयोग करके लक्ष्य में परिवर्तित किया जा सकता है -

• इंक्रीमेंट ऑपरेशन - सभी तत्वों को 1 से बढ़ाया जा सकता है, प्रत्येक इंक्रीमेंट ऑपरेशन को चरणों में व्यक्तिगत रूप से गिना जा सकता है। ( n तत्वों में n वृद्धि के लिए steps=n )

• दोहरीकरण ऑपरेशन - पूरे सरणी को दोगुना कर दिया जाता है। सभी तत्वों के लिए इसे एक बार गिना जाता है। (प्रत्येक दोहरीकरण ऑपरेशन सभी तत्वों के मान को दोगुना कर देता है, इसे चरणों में 1 के रूप में गिनें

लक्ष्य लक्ष्य तक पहुँचने के लिए न्यूनतम चरणों की संख्या ज्ञात करना है। जैसे [0,0,0] न्यूनतम 3 चरणों में [1,1,1] बन सकता है (सभी तत्वों पर वृद्धि संचालन द्वारा) और एक और दोहरीकरण ऑपरेशन द्वारा [2,2,2] बन सकता है, इस बार कुल 4 कदम ( 3 वेतन वृद्धि, 1 दोहरीकरण ).

इनपुट

target[]= { 1,2,2,3 }

आउटपुट

Minimum steps to reach target from {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 }

आउटपुट

Minimum steps to reach target from {0,0,0} : 7

स्पष्टीकरण

प्रारंभ में हमारे पास { 0,0,0 }

3 वेतन वृद्धि संचालन { 1,1,1 } // वेतन वृद्धि व्यक्तिगत रूप से होती है

1 दोहरीकरण ऑपरेशन { 2,2,2 } // सभी तत्वों पर दोहरीकरण होता है

3 इंक्रीमेंट ऑपरेशन { 3,3,3 }

कुल चरण=3+1+3=7

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• पूर्णांक सरणी लक्ष्य [] लक्ष्य तत्वों तक पहुँचने के लिए संग्रहीत करता है।

• फ़ंक्शन minSteps(int target[],int n) लक्ष्य सरणी और उसकी लंबाई 'n' को इनपुट के रूप में लेता है और सभी शून्य से लक्ष्य तक पहुंचने के लिए न्यूनतम चरणों की गिनती देता है।

• वैरिएबल काउंट का इस्तेमाल स्टेप काउंट को स्टोर करने के लिए किया जाता है, शुरुआत में 0.

• वेरिएबल मैक्स का उपयोग उच्चतम तत्व को स्टोर करने के लिए किया जाता है, प्रारंभ में लक्ष्य [0]।

• वेरिएबल पॉज़ का उपयोग प्रारंभ में अधिकतम 0 के सूचकांक को संग्रहीत करने के लिए किया जाता है।

• यदि लक्ष्य [] सरणी में सभी शून्य हैं तो 0 को बिना किसी चरण की आवश्यकता के वापस करें। ( के लिए (i=0;i

• अब इस दृष्टिकोण में हम लक्ष्य [] से सभी शून्य तक पहुंचेंगे।

• विषम तत्वों में से 1 घटाकर भी सभी अवयव बनाएं। प्रत्येक घटाव के लिए वृद्धि गणना (वृद्धि संचालन के समान)

• अब हमारे पास सभी सम संख्याएँ हैं।

• साथ ही एक ही लूप में अधिकतम मान और उसकी स्थिति का पता लगाएं और अधिकतम और पॉज़ को इनिशियलाइज़ करें।

• अब हम पूरे सरणी को 2 से विभाजित करना शुरू करते हैं जब तक कि अधिकतम मान 1 न हो जाए। यदि कोई संख्या विषम हो जाती है, तो 1 घटाएं और गिनती बढ़ाएं, पूरे विभाजन ऑपरेशन के लिए एक बार वृद्धि की गणना करें।

• अंत में सभी तत्व या तो 0 या 1 होंगे, क्योंकि सभी 1 उन्हें 0 बनाते हैं और फिर से वृद्धि की गणना करते हैं।

• गणना में मौजूद चरणों के रूप में परिणाम लौटाएं।

उदाहरण

#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<n;i++)
      if(target[i]==0)
         count++;
      //if all are zeros, same as target
      if(count==n)
         return 0;
         count=0;
         //make all even by sbtracting 1
      for(i=0;i<n;i++){
         if(target[i]%2==1){
            target[i]=target[i]-1;
            count++;
      }
      //find max value and its position
      if(target[i]>=max){
         max=target[i];
         pos=i;
      }
   }
   //diving by 2 till all elements are 1 and increase count once
   while(target[pos]!=1){
      for(i=0;i<n;i++){
         if(target[i]%2==1){
             target[i]=target[i]-1;
            count++;
      }
      target[i]=target[i]/2;
   }
   count++;
}
//whole array is {1} make zeroes and increase count
while(target[pos]!=0){
   for(i=0;i<n;i++){
      if(target[i]!=0){
         target[i]=target[i]-1;
         count++;}
      }
   }
   return count;
}
int main(){
   int target[]={15,15,15};
   cout<<"\nMinimum steps to get the given desired array:"<<minSteps(target,3);
   return 0;
}

आउटपुट

Minimum steps to get the given desired array:15