Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में केवल रोटेशन की अनुमति देकर Sum(i*arr[i]) का अधिकतम मान ज्ञात करें


इस समस्या में, हमें n तत्वों वाली एक सरणी arr[] दी गई है। हमें केवल दी गई सरणी पर रोटेशन की अनुमति देकर Sum(i*arr[i]) का अधिकतम मान ज्ञात करना है। (i*arr[i]) का अधिकतम योग खोजने के लिए, हम किसी भी संख्या में रोटेशन कर सकते हैं।

आइए एक उदाहरण से समझते हैं:

इनपुट

arr[] = {4, 1, 3, 7, 2}

आउटपुट

43

व्याख्या

हम अधिकतम मान प्राप्त करने के लिए सरणी को एक बार घुमाएँगे, रोटेशन के बाद सरणी {2, 4, 1, 3, 7} होगी।

योग = 0*2 + 1*4 + 2*1 + 3*3 + 4*7 = 0 + 4 + 2 + 9 + 28 = 43

समाधान दृष्टिकोण

समस्या का एक सरल समाधान सरणी को n बार घुमाना है। प्रत्येक रोटेशन के बाद, हम sum(i*arr[i]) खोजेंगे और सभी मानों में से अधिकतम लौटाएँगे। यह अच्छा है लेकिन समय जटिलता O(n²) क्रम की है। एक अधिक कुशल समाधान सूत्र का उपयोग करके रोटेशन के बिना sum(i*arr[i]) का मान खोजना है।

आइए सूत्र को गणितीय रूप से प्राप्त करें:

मान लें कि k रोटेशन के बाद योग sum(k) के बराबर है। sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => समीकरण 1

अब, हम मानों को घुमाएँगे जिसके बाद योग बन जाएगा,

sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => समीकरण 2 समीकरण 2 - समीकरण 1 घटाने पर sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]

इसी तरह sum(2) - sum(1) के लिए,

sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]

समीकरण को सामान्यीकृत करने पर,

sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]

इसका उपयोग करके हम sum(0) का उपयोग करके sum(k) का मान खोज सकते हैं।

अब, समाधान में हम सरणी के सभी मानों का योग खोजेंगे, फिर sum(0) का मान खोजेंगे। एक लूप का उपयोग करके, हम 1 से n तक sum(k) के सभी मान खोजेंगे। और उनमें से अधिकतम लौटाएँगे।

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:

उदाहरण

#include <iostream> using namespace std; int findMaxSumRotation(int arr[], int n){    int arrSum = 0;    int currSum = 0;    for (int i=0; i<n; i++){       arrSum = arrSum + arr[i];       currSum = currSum+(i*arr[i]);    }    int maxSum = currSum;    for (int j=1; j<n; j++){       currSum = currSum + arrSum-n*arr[n-j];       if (currSum > maxSum)          maxSum = currSum;    }    return maxSum; } int main(){    int arr[] = {4, 1, 3, 7, 2};    int n = sizeof(arr)/sizeof(arr[0]);    cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);    return 0; }

आउटपुट

The maximum value of sum(i*arr[i]) using rotations is 43

  1. - C++ में दिए गए योग के साथ अधिकतम आकार का सबसेट

    समस्या कथनN तत्वों का एक एरे और योग दिया गया है। हमें उस अधिकतम आकार के सबसेट का आकार ढूंढना है जिसका योग दिए गए योग के बराबर हो।उदाहरणयदि इनपुट एरे arr = { 2, 3, 5, 10 } है और योग = 20 है तो आउटपुट 4 होगा क्योंकि −2 + 3 + 5 + 10 = 20 जो दिए गए योग के बराबर है।एल्गोरिदमहम इस समस्या को हल करने

  1. - C++ में दिए गए ऑपरेशन से ऐरे योग को अधिकतम करना

    विवरण (2 * n - 1) पूर्णांकों का एक ऐरे है। हम ऐरे में ठीक n तत्वों का चिन्ह बदल सकते हैं। दूसरे शब्दों में, हम ठीक n ऐरे तत्वों का चयन कर सकते हैं, और उनमें से प्रत्येक को -1 से गुणा कर सकते हैं। ऐरे का अधिकतम योग ज्ञात करें। उदाहरण यदि इनपुट ऐरे है {-2, 100, -3} तो हम -2 और -3 का चिन्ह बदलकर अधिक

  1. - C++ में सरणी में अधिकतम GCD वाली जोड़ी ढूंढना

    मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी है। हमारा कार्य सरणी से पूर्णांकों की जोड़ी ढूंढना है, जहां GCD मान अधिकतम है। मान लीजिए A = {1, 2, 3, 4, 5}, तो आउटपुट 2 है। जोड़ी (2, 4) का GCD 2 है, अन्य GCD मान 2 से कम हैं।इस समस्या को हल करने के लिए, हम एक काउंट सरणी बनाए रखेंगे जो प्रत्येक तत्