मान लीजिए कि हमारे पास n तत्वों की एक सरणी है। सभी तत्वों का अधिकतम संभव योग इस प्रकार ज्ञात कीजिए कि सभी तत्व समान हों। केवल संचालन जिसकी अनुमति है वह है किन्हीं दो तत्वों को चुनना और उनमें से बड़े को दो के पूर्ण अंतर से बदलना। मान लीजिए कि तत्व [9, 12, 3, 6] जैसे हैं। फिर आउटपुट 12 होगा। तो पहले ए [1] को ए [1] - ए [3] =12 - 6 =6 से बदलें। तो अब तत्व [9, 6, 3, 6] हैं, फिर ए को बदलें [ 3] ए के साथ [3] - ए [2] =6 - 3 =3। तो तत्व [9, 6, 3, 3] हैं। फिर ए [0] को ए [0] - ए [1] =9 - 6 =3 से बदलें। तो तत्व [3, 6, 3, 3] हैं। और अंत में A[1] को A[1] - A[3] =6 - 3 =3 से बदलें। तो तत्व [3, 3, 3, 3] हैं। तो सब एक जैसे हैं। और योग 12
. हैयदि हम संक्रिया का विश्लेषण करते हैं, तो यह A[i] =A[i] – A[j] होगा, जहां A[i]> A[j]। तो हम दो संख्याएँ लेंगे, फिर बड़े मान को उनके निरपेक्ष अंतर से बदल देंगे। फिर इन चरणों को तब तक दोहराएं जब तक कि सभी समान न हो जाएं।
उदाहरण
#include<iostream>
#include<algorithm>
using namespace std;
int findSameElement(int arr[], int n) {
int gcd_val = arr[0];
for (int i = 1; i < n; i++)
gcd_val = __gcd(arr[i], gcd_val);
return gcd_val;
}
int getMaxSum(int arr[], int n) {
int value = findSameElement(arr, n);
return (value * n);
}
int main() {
int arr[] = {3, 9, 6, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum sum is: " << getMaxSum(arr, n);
} आउटपुट
The maximum sum is: 12