কে-এলিমেন্টের গ্রুপ এবং সি-তে বাকি অ্যারের মধ্যে সর্বাধিক পার্থক্য

আমাদের N আকারের পূর্ণসংখ্যার একটি বিন্যাস এবং একটি সংখ্যা k দেওয়া হয়েছে৷ অ্যারে এলোমেলো ক্রমে পূর্ণসংখ্যা নিয়ে গঠিত। কাজটি হল k-এলিমেন্টের গ্রুপ এবং বাকি অ্যারের মধ্যে সর্বাধিক পার্থক্য খুঁজে বের করা। অ্যারে দুটি ভাগে বিভক্ত হবে। প্রথম অংশটি কে-এলিমেন্টের একটি গ্রুপ বের করা হয়েছে এবং দ্বিতীয় অংশটি অ্যারের বাকি উপাদানগুলি। আমাদের k উপাদান নির্বাচন করতে হবে যাতে উভয় গ্রুপের উপাদানগুলির যোগফলের মধ্যে পার্থক্য সর্বাধিক হয়।

যদি k ছোট হয় (<=অ্যারের আকারের অর্ধেক) তাহলে সবচেয়ে ছোট k উপাদানের সর্বনিম্ন যোগফল হবে এবং বাকি N-k উপাদানগুলির যোগফল সবচেয়ে বেশি হবে। সুতরাং সর্বাধিক পার্থক্য হল − (বাকী N-k উপাদানের যোগফল) - (সবচেয়ে ছোট k-উপাদানের যোগফল)।

যদি k বড় হয় (> অ্যারের আকারের অর্ধেক) তাহলে সবচেয়ে বড় k উপাদানগুলির যোগফল সবচেয়ে বেশি হবে এবং বাকি N-k উপাদানগুলির সর্বনিম্ন যোগফল থাকবে। তাই সর্বাধিক পার্থক্য হল (সবচেয়ে বড় কেলিমেন্টের যোগফল) - (বাকি N-k উপাদানের যোগফল)।

ইনপুট

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

আউটপুট − k-এলিমেন্টের গ্রুপ এবং বাকি অ্যারের মধ্যে সর্বোচ্চ পার্থক্য − 16

ব্যাখ্যা − এখানে k ছোট তাই সর্বনিম্ন ৩টি সংখ্যার যোগফল সবচেয়ে ছোট হবে।

সর্বনিম্ন 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=

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ

• পূর্ণসংখ্যার একটি অ্যারে ঘোষণা করুন যা এলোমেলো ক্রমে ধারণ করে।( Arr[] )

• অ্যারের আকার সংরক্ষণ করার জন্য একটি ভেরিয়েবল তৈরি করুন। (N)

• ফাংশন maxKDiff( int Arr[],int n, int k) একটি অ্যারের মধ্যে একটি উপাদানের প্রথম এবং শেষ সূচকগুলির মধ্যে সর্বাধিক পার্থক্য (maxD) গণনা করতে ব্যবহৃত হয়৷

• পুরো অ্যারের যোগফল গণনা করুন এবং আরসামে সংরক্ষণ করুন।

• প্রথম জিনিসটি হল ন্যূনতম k উপাদানগুলির যোগফল গণনা করা। লুপের জন্য ব্যবহার করা হচ্ছে ( i=0;i

  k ছোট হলে সবচেয়ে ছোট k উপাদানের সর্বনিম্ন যোগফল −

  হবে

• D1-এ abs((পুরো অ্যারের যোগফল) - (2*সর্বনিম্ন k উপাদানের যোগফল))। দুবার কারণ অ্যারের সমষ্টিতেও এই উপাদানগুলি রয়েছে৷

  ৷

  k এর চেয়ে বড় k উপাদানের সর্বোচ্চ যোগফল −

  হবে

• D2-এ abs((পুরো অ্যারের যোগফল) - (2*সর্বোচ্চ k উপাদানের যোগফল))। দুবার কারণ অ্যারের সমষ্টিতেও এই উপাদানগুলি রয়েছে৷

  ৷

• D2 এর সাথে D1 তুলনা করুন এবং সর্বাধিক মান 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