অ্যারের সব এলিমেন্ট ৪ দিয়ে বিভাজ্য করার ন্যূনতম ধাপ C++-তে

সমস্যা বিবরণ

আকার n এর একটি অ্যারে দেওয়া আছে, কাজ হলো অ্যারের সব এলিমেন্ট ৪ দিয়ে বিভাজ্য করার জন্য ন্যূনতম ধাপ সংখ্যা বের করা। একটি ধাপ বলতে অ্যারে থেকে যেকোনো দুটি এলিমেন্ট সরিয়ে তাদের যোগফল অ্যারেতে যোগ করা বোঝায়।

উদাহরণ

ইনপুট অ্যারে {1, 2, 0, 2, 4, 3} হলে ৩টি অপারেশন দরকার:

1 + 3 = 4
2 + 2 = 4
0 + 4 = 4

অ্যালগরিদম

1. অ্যারের সব এলিমেন্টের যোগফল ৪ দিয়ে বিভাজ্য হতে হবে। যদি না হয়, তবে এই টাস্ক সম্ভব নয়।
2. modulus নামক আকার ৪ এর একটি অ্যারে ০ দিয়ে ইনিশিয়ালাইজ করুন।
3. একটি কাউন্টার ০ দিয়ে ইনিশিয়ালাইজ করুন। এটি ধাপ সংখ্যা ট্র্যাক করবে।
4. ইনপুট অ্যারে ট্র্যাভার্স করে প্রতিটি এলিমেন্টের মডুলাস ৪ নিন।
5. modulus অ্যারেতে মড ৪ ভ্যালুর মান ১ বাড়ান।
6. modulus[0] হলো ইতিমধ্যে ৪ দিয়ে বিভাজ্য এলিমেন্টের কাউন্ট। সেগুলো অন্য এলিমেন্টের সাথে পেয়ার করার দরকার নেই।
7. modulus[1] এবং modulus[3] এলিমেন্টগুলো মিলিয়ে ৪ দিয়ে বিভাজ্য সংখ্যা পাওয়া যায়। তাই উভয়ের ন্যূনতম মান কাউন্টে যোগ করুন।
8. modulus[2] এর প্রতি ২টি এলিমেন্ট মিলিয়ে ৪ দিয়ে বিভাজ্য এলিমেন্ট পাওয়া যায়।
9. বাকি এলিমেন্টের জন্য, modulus[2]-এ modulus[1] এবং modulus[3]-এর অর্ধেক যোগ করুন।
10. এখন কাউন্টে modulus[2]-এর অর্ধেক যোগ করুন। অর্ধেক নেওয়া হয় কারণ প্রতি ২টি এলিমেন্ট ১টি হয়ে যাচ্ছে।
11. কাউন্টের চূড়ান্ত মান হলো ইনপুট অ্যারের সব এলিমেন্ট ৪ দিয়ে বিভাজ্য করার জন্য প্রয়োজনীয় ধাপ সংখ্যা।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(int arr[], int n) {
    int count = 0;
    int modulus[4] = {0};
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int mod = arr[i] % 4;
        sum += mod;
        modulus[mod]++;
    }
    if (sum % 4 != 0) {
        return -1;
    } else {
        if (modulus[1] > modulus[3]) {
            count += modulus[3];
        } else {
            count += modulus[1];
        }
        modulus[1] -= count;
        modulus[3] -= count;
        modulus[2] += modulus[1] / 2;
        modulus[2] += modulus[3] / 2;
        count += modulus[1] / 2;
        count += modulus[3] / 2;
        count += modulus[2] / 2;
        return count;
    }
}
int main() {
    int arr[] = {1, 2, 0, 2, 4, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum required steps = " << getMinRequiredSteps(arr, n) << endl;
    return 0;
}

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

আউটপুট

Minimum required steps = 2