একটি পূর্ণসংখ্যার অ্যারে (সাইজ N) এবং একটি সংখ্যা k দেওয়া আছে। অ্যারেকে দুটি গোষ্ঠীতে ভাগ করতে হবে: একটি k-উপাদানের গোষ্ঠী এবং বাকি N-k উপাদান। লক্ষ্য হলো k উপাদান এমনভাবে বেছে নেওয়া যাতে দুটি গোষ্ঠীর যোগফলের পার্থক্য সর্বোচ্চ হয়।
লজিক
- যদি k ≤ N/2 হয়: ক্ষুদ্রতম k উপাদান বেছে নিলে তাদের যোগফল সর্বনিম্ন হবে, বাকি N-k উপাদানের যোগফল সর্বাধিক। পার্থক্য = (বাকি যোগফল) - (ক্ষুদ্রতম k যোগফল)।
- যদি k > N/2 হয়: সর্বাধিক k উপাদান বেছে নিলে তাদের যোগফল সর্বাধিক হবে, বাকি N-k উপাদানের যোগফল সর্বনিম্ন। পার্থক্য = (সর্বাধিক k যোগফল) - (বাকি যোগফল)।
উদাহরণ
ইনপুট: Arr[] = { 2, 5, 6, 1, 3, 2, 1, 4 }, k = 3
আউটপুট: সর্বোচ্চ পার্থক্য - 16
ব্যাখ্যা: k=3 (≤4)। ক্ষুদ্রতম ৩টি: 1, 1, 2 → যোগফল=৪। বাকি ৫টি: 2, 3, 4, 5, 6 → যোগফল=২০। পার্থক্য = ২০-৪ = ১৬।
ইনপুট: Arr[] = { 2, 2, 3, 4, 8, 3, 4, 4, 8, 7 }, k = 6
আউটপুট: ২৫
ব্যাখ্যা: k=6 (>5)। সর্বাধিক ৬টি: 8, 8, 7, 4, 4, 4 → যোগফল=৩৫। বাকি ৪টি: 2, 2, 3, 3 → যোগফল=১০। পার্থক্য = ৩৫-১০ = ২৫।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- অ্যারে Arr[] এবং সাইজ N, k ইনপুট।
- maxKDiff(int Arr[], int n, int k) ফাংশনটি পার্থক্য হিসাব করে।
- পুরো অ্যারের যোগফল arrsum-এ রাখা হয়।
- অ্যারে সোর্ট করা হয় (আরোহী ক্রমে)।
- প্রথম k টি (ক্ষুদ্রতম) যোগফল sumk-এ, D1 = |arrsum - 2*sumk|।
- শেষ k টি (সর্বাধিক) যোগফল sumk-এ, D2 = |arrsum - 2*sumk|।
- maxD = max(D1, D2) রিটার্ন করা হয়।
C প্রোগ্রাম উদাহরণ
#include <stdio.h>
#include <math.h>
int maxKDiff(int arr[], int n, int k) {
int arrsum = 0;
for (int i = 0; i < n; i++) arrsum += arr[i];
int sumk = 0;
for (int i = 0; i < k; i++) sumk += arr[i];
int D1 = abs(arrsum - 2 * sumk);
sumk = 0;
for (int i = n - 1, j = 0; j < k; i--, j++) sumk += arr[i];
int D2 = abs(arrsum - 2 * sumk);
return D1 > D2 ? D1 : D2;
}
int main() {
int arr[] = {2, 3, 2, 10, 7, 12, 8};
int n = 7, k = 3;
// sort(arr, n) ধরে নেওয়া হয়েছে
printf("সর্বোচ্চ পার্থক্য: %d", maxKDiff(arr, n, k));
return 0;
}
আউটপুট
সর্বোচ্চ পার্থক্য: 30
