একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে দেওয়া থাকলে, সেটিকে রি-অ্যারেঞ্জ করতে হবে যাতে প্রতিটি লิงক এলিমেন্টকে তার পরের এলিমেন্ট দিয়ে গুণ করে যোগফল ন্যূনতম হয়।
উদাহরণ
ইনপুট − arr[] = {2,5,1,7,5,0,1,0}
আউটপুট − 7 0 5 0 5 1 2 1 (যোগফল = 7)
ব্যাখ্যা − 7×0 + 5×0 + 5×1 + 2×1 = 7।
ইনপুট − arr[] = {1,3,7,2,4,3}
আউটপুট − 7 1 4 2 3 3 (যোগফল = 24)
ব্যাখ্যা − 7×1 + 4×2 + 3×3 = 24।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
অ্যারে সর্ট করুন।
আধা ছোট মান
oddভেক্টরে, বাকি বড় মানevenভেক্টরে রাখুন।evenকে ডিসেন্ডিং অর্ডারে সর্ট করুন।এবার
even[j]ওodd[j]বारी বاری অ্যারেতে রাখুন।যোগফল
total += even[j] * odd[j]।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int Rearrange_min_sum(int arr[], int size){
vector even, odd;
int temp = 0, total = 0;
for(int i = 0; i < size; i++){
if (i < size/2) odd.push_back(arr[i]);
else even.push_back(arr[i]);
}
sort(even.begin(), even.end(), greater());
for(int j = 0; j < even.size(); j++){
arr[temp++] = even[j];
arr[temp++] = odd[j];
total += even[j] * odd[j];
}
return total;
}
int main(){
int arr[] = {2, 5, 1, 7, 5, 0, 1, 0};
int size = sizeof(arr)/sizeof(arr[0]);
sort(arr, arr + size);
int total = Rearrange_min_sum(arr, size);
cout << "Rearrangement of an array to minimize sum i.e. " << total << " of product of consecutive pair elements is: ";
for(int i = 0; i < size; i++) cout << arr[i] << " ";
return 0;
}
আউটপুট
উপরের কোড রান করলে নিচের আউটপুট পাওয়া যাবে:
Rearrangement of an array to minimize sum i.e. 7 of product of consecutive pair elements is: 7 0 5 0 5 1 2 1
