हमें आकार N की पूर्णांकों की एक सरणी और एक संख्या k दी गई है। सरणी में पूर्णांक यादृच्छिक क्रम में होते हैं। कार्य k-तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर ढूंढना है। सरणी को दो भागों में विभाजित किया जाएगा। पहला भाग k-तत्वों का समूह है जिसे निकाला जाता है और दूसरा भाग सरणी के शेष तत्व हैं। हमें k तत्वों का चयन करना है ताकि दोनों समूहों में तत्वों के योग का अंतर अधिकतम हो।
यदि k छोटा है (<= सरणी आकार का आधा) तो सबसे छोटे k तत्वों का योग सबसे कम होगा और शेष N-k तत्वों का योग सबसे बड़ा होगा। इसलिए अधिकतम अंतर है - (शेष N-k तत्वों का योग) - (सबसे छोटे k-तत्वों का योग)।
यदि k बड़ा है (> सरणी आकार का आधा) तो सबसे बड़े k तत्वों का योग सबसे अधिक होगा और शेष N-k तत्वों का योग सबसे कम होगा। इसलिए अधिकतम अंतर है (सबसे बड़े k-तत्वों का योग) - (शेष N-k तत्वों का योग)।
इनपुट
Arr[] = { 2, 5, 6, 1, 3, 2, 1, 4 }. k = 3 आउटपुट
k-तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर: 16
व्याख्या
यहां k छोटा है इसलिए सबसे कम 3 संख्याओं का योग सबसे छोटा होगा।
सबसे कम 3 संख्याएं - 1, 1, 2 योग = 4
शेष N-k = 5 संख्याएं: 2, 3, 4, 5, 6 योग = 20
अधिकतम अंतर: 20 - 4 = 16
इनपुट
Arr[] = { 2, 2, 3, 4, 8, 3, 4, 4, 8, 7 }. k = 6 आउटपुट
k-तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर: 25
व्याख्या
यहां k बड़ा है इसलिए सबसे बड़ी 6 संख्याओं का योग सबसे अधिक होगा।
सबसे बड़ी 6 संख्याएं - 8, 8, 7, 4, 4, 4, योग = 35
शेष N-k = 4 संख्याएं - 2, 2, 3, 3 योग = 10
अधिकतम अंतर: 35 - 10 = 25
उपयोग किया गया दृष्टिकोण
यादृच्छिक क्रम में पूर्णांकों की एक सरणी घोषित करें (Arr[])।
सरणी के आकार को संग्रहीत करने के लिए एक चर बनाएं (N)।
फ़ंक्शन maxKDiff(int Arr[], int n, int k) सरणी में एक तत्व के पहले और अंतिम सूचकांकों के बीच अधिकतम अंतर (maxD) की गणना के लिए उपयोग किया जाता है।
पूरी सरणी का योग निकालें और arrsum में संग्रहीत करें।
पहली बात है सबसे छोटे k तत्वों का योग निकालना। फॉर लूप का उपयोग करके (i = 0; i < k)।
यदि k छोटा है तो सबसे छोटे k तत्वों का योग सबसे कम होगा।
D1 में abs((पूरी सरणी का योग) - (2 * सबसे छोटे k तत्वों का योग)) संग्रहीत करें। दो बार क्योंकि सरणी के योग में ये तत्व भी शामिल हैं।
यदि k बड़ा है तो सबसे बड़े k तत्वों का योग सबसे अधिक होगा।
D2 में abs((पूरी सरणी का योग) - (2 * सबसे बड़े k तत्वों का योग)) संग्रहीत करें। दो बार क्योंकि सरणी के योग में ये तत्व भी शामिल हैं।
D1 की तुलना D2 से करें और अधिकतम मान maxD में संग्रहीत करें।
परिणाम के रूप में maxD लौटाएं।
उदाहरण
#include <stdio.h> #include <math.h> // सरणी के अधिकतम समूह अंतर के लिए फ़ंक्शन int maxKDiff(int arr[], int n, int k){ // सरणी का योग int arrsum = 0; int i; for(i = 0; i < n; i++) arrsum += arr[i]; // सबसे छोटे k का योग int sumk = 0; for(i = 0; i < k; i++) sumk += arr[i]; // k-सबसे छोटे के लिए अंतर int D1 = abs(arrsum - 2 * sumk); // सबसे बड़े k तत्वों का योग sumk = 0; int j = 0; for(i = n - 1; j < k; i--){ sumk += arr[i]; j++; } // k-सबसे बड़े के लिए अंतर int D2 = abs(arrsum - 2 * sumk); int maxD = D1 >= D2 ? D1 : D2; // अधिकतम अंतर मान लौटाएं return maxD; } // ड्राइवर प्रोग्राम int main(){ int arr[] = { 2, 3, 2, 10, 7, 12, 8 }; int n = 7; int k = 3; sort(arr, n); // सरणी को आरोही क्रम में सॉर्ट करने के लिए printf("k-तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर: %d", maxKDiff(arr, n, k)); return 0; } आउटपुट
उपरोक्त कोड चलाने पर निम्नलिखित आउटपुट उत्पन्न होगा:
k-तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर: 30
