के-तत्वों के समूह और सी में शेष सरणी के बीच अधिकतम अंतर

हमें आकार N और एक संख्या k के पूर्णांकों की एक सरणी दी गई है। सरणी में यादृच्छिक क्रम में पूर्णांक होते हैं। कार्य k- तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर ज्ञात करना है। सरणी को दो भागों में विभाजित किया जाएगा। पहला भाग निकाले गए k- तत्वों का एक समूह है और दूसरा भाग सरणी के शेष तत्व हैं। हमें k तत्वों का चयन इस तरह करना है कि दोनों समूहों में तत्वों के योग के बीच का अंतर अधिकतम हो।

यदि k छोटा है (<=सरणी आकार का आधा) तो सबसे छोटे k तत्वों का योग न्यूनतम होगा और शेष N-k तत्वों का योग सबसे बड़ा होगा। तो अधिकतम अंतर है - (बाकी एन-के तत्वों का योग) - (सबसे छोटे के-तत्वों का योग)।

यदि k बड़ा है (> सरणी आकार का आधा) तो सबसे बड़े k तत्वों का योग सबसे बड़ा होगा और शेष N-k तत्वों का योग सबसे कम होगा। तो अधिकतम अंतर है (सबसे बड़े तत्वों का योग) - (बाकी एन-के तत्वों का योग)।

इनपुट

Arr[] = { 2,5,6,1,3,2,1,4 }. k=3

आउटपुट - k-तत्वों के समूह और शेष सरणी के बीच अधिकतम अंतर - 16

स्पष्टीकरण − यहाँ k छोटा है इसलिए कम से कम 3 संख्याओं का योग सबसे छोटा होगा।

कम से कम 3 संख्याएं - 1,1,2 योग=4

बाकी एन-के =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=

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

• पूर्णांकों की एक सरणी घोषित करें जिसमें यादृच्छिक क्रम हो। ( Arr[] )

• सरणी के आकार को संग्रहीत करने के लिए एक चर बनाएँ। (एन)

• फ़ंक्शन maxKDiff(int Arr[],int n, int k) का उपयोग किसी सरणी में किसी तत्व के पहले और अंतिम इंडेक्स के बीच अधिकतम अंतर (maxD) की गणना करने के लिए किया जाता है।

• संपूर्ण सरणी के योग की गणना करें और arrsum में संग्रहीत करें।

• पहली बात कम से कम k तत्वों के योग की गणना करना है। लूप के लिए उपयोग करना ( i=0;i

  यदि k छोटा है तो सबसे छोटे k तत्वों का योग न्यूनतम होगा -

• D1 में एब्स ((पूरे सरणी का योग) - (2 * कम से कम k तत्वों का योग)) स्टोर करें। दो बार क्योंकि सरणी योग में भी ये तत्व होते हैं।

  k बड़ा है तो सबसे बड़े k तत्वों का योग उच्चतम होगा -

• D2 में एब्स ((पूरे एरे का योग) - (2 * उच्चतम k तत्वों का योग)) स्टोर करें। दो बार क्योंकि सरणी योग में भी ये तत्व होते हैं।

• D1 की D2 से तुलना करें और अधिकतम मान को maxD में संग्रहित करें।

• परिणाम के रूप में maxD लौटाएं।

उदाहरण

#include <stdio.h>
#include <math.h>
// function for finding maximum group difference of array
int maxKDiff (int arr[], int n, int k){
   // sum of array
   int arrsum = 0;
   int i;
   for(i=0;i<n;i++)
      arrsum+=arr[i];
   //sum of smallest k
   int sumk=0;
   for(i=0;i<k;i++)
      sumk+=arr[i];
   // difference for k-smallest
   int D1 = abs(arrsum - 2*sumk);
   //sum of largest k elements
   sumk=0;
   int j=0;
   for(i=n-1;j<4;i--){
      sumk+=arr[i]; j++;
   }
   // difference for k-largest
   int D2 = abs(arrsum - 2*sumk);
   int maxD=D1>=D2?D1:D2;
   // return maximum difference value
   return maxD;
}
// driver program
int main(){
   int arr[] ={ 2,3,2,10,7,12,8};
   int n = 7;
   int k = 3;
   sort(arr,n); // to sort array in ascending order
   printf("Maximum difference between the group of k-elements and rest of the array : %d" , maxKDiff(arr,n,k));
   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -

Maximum difference between the group of k-elements and rest of the array : 30