ম্যাট্রিক্সের সব এলিমেন্ট সমান করার ন্যূনতম অপারেশন C++-তে

সমস্যা বিবরণ

একটি ইন্টিজার K এবং M x N ম্যাট্রিক্স দেওয়া আছে। কাজ হলো ম্যাট্রিক্সের সব এলিমেন্ট সমান করার জন্য ন্যূনতম অপারেশন সংখ্যা বের করা। এক অপারেশনে K কোনো এলিমেন্টে যোগ বা বিয়োগ করা যায়।

উদাহরণ

ইনপুট ম্যাট্রিক্স: { {2, 4}, {20, 40} } এবং K = 2 হলে মোট ২৭ অপারেশন দরকার:
Matrix[0][0] = 2 + (K * 9) = 20 = 9 অপারেশন
Matrix[0][1] = 4 + (k * 8) = 20 = 8 অপারেশন
Matrix[1][0] = 20 + (k * 10) = 40 = 10 অপারেশন

অ্যালগরিদম

1. যেহেতু শুধু K যোগ বা বিয়োগ করা যায়, তাই সব এলিমেন্টের K দিয়ে মড সমান হতে হবে। না হলে -1 রিটার্ন।
2. ম্যাট্রিক্সের সব এলিমেন্ট নন-ডিক্রিজিং অর্ডারে সর্ট করুন এবং মিডিয়ান বের করুন।
3. ন্যূনতম ধাপ হবে যদি সব এলিমেন্ট মিডিয়ানের সমান করা হয়।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
int getMinOperations(int n, int m, int k, vector>& matrix) {
    vector arr(n * m, 0);
    int mod = matrix[0][0] % k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            arr[i * m + j] = matrix[i][j];
            if (matrix[i][j] % k != mod) {
                return -1;
            }
        }
    }
    sort(arr.begin(), arr.end());
    int median = arr[(n * m) / 2];
    int minOperations = 0;
    for (int i = 0; i < n * m; ++i)
        minOperations += abs(arr[i] - median) / k;
    if ((n * m) % 2 == 0) {
        int newMedian = arr[(n * m) / 2];
        int newMinOperations = 0;
        for (int i = 0; i < n * m; ++i)
            newMinOperations += abs(arr[i] - newMedian) / k;
        minOperations = min(minOperations, newMinOperations);
    }
    return minOperations;
}
int main() {
    vector> matrix = {
        { 2, 4},
        { 20, 40},
    };
    int n = matrix.size();
    int m = matrix[0].size();
    int k = 2;
    cout << "Minimum required operations = " << getMinOperations(n, m, k, matrix) << endl;
    return 0;
}

উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে

আউটপুট

Minimum required operations = 27