C++ প্রোগ্রাম: XOR যোগফলের সর্বোচ্চ সম্ভাব্য মান খুঁজে বের করা

মান লিখুন: আমাদের কাছে N উপাদান বিশিষ্ট একটি অ্যারে A এবং আরেকটি মান K রয়েছে। 0 থেকে K পরিসরের পূর্ণসংখ্যা X-এর জন্য f(X) = (X xor A[1]) + (X xor A[2]) + ... + (X xor A[N])। f(X)-এর সর্বোচ্চ সম্ভাব্য মান বের করতে হবে।

উদাহরণ

যদি ইনপুট হয় K = 7; A = [1, 6, 3], তবে আউটপুট হবে 14, কারণ f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14।

সমাধানের ধাপসমূহ

n := A এর আকার
for i := 45 থেকে 0 পর্যন্ত (হ্রাসমান):
    p := 2^i
    m := 0
    for j := 0 থেকে n-1:
        যদি A[j] & p নন-জিরো: m++
    যদি o + p <= k:
        যদি m < n - m:
            m := n - m
            o := o + p
    d := d + p * m
d রিটার্ন করুন

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

long solve(int k, vector<int> A) {
    long n = A.size(), d = 0, m, p, o = 0;
    for (long i = 45; i >= 0; i--) {
        p = pow(2, i);
        m = 0;
        for (int j = 0; j < n; j++) {
            if (A[j] & p) m++;
        }
        if (o + p <= k) {
            if (m < n - m) {
                m = n - m;
                o += p;
            }
        }
        d += p * m;
    }
    return d;
}

int main() {
    int K = 7;
    vector<int> A = { 1, 6, 3 };
    cout << solve(K, A) << endl;
}

ইনপুট

7, { 1, 6, 3 }