C++-এ বিটওয়াইজ AND শূন্য হয় এমন ট্রিপলেটের সংখ্যা

সমস্যা বিবরণ

একটি ইন্টিজার অ্যারে A দেওয়া থাকলে, (i, j, k) ট্রিপলেটের সংখ্যা বের করতে হবে যাতে A[i] & A[j] & A[k] == 0। এখানে & হলো বিটওয়াইজ AND অপারেটর।

উদাহরণ

A = [3,1,2] → আউটপুট = 12

সমাধান পদ্ধতি

• সব যুগল (i, j) এর জন্য A[i] & A[j] গণনা করে ফ্রিকোয়েন্সি ম্যাপে স্টোর করা হয়।
• তারপর প্রতিটি x = A[i] এর জন্য ম্যাপে থাকা যেসব key-এর সাথে x-এর AND শূন্য, তাদের ফ্রিকোয়েন্সি যোগ করা হয়।
• সময় জটিলতা: O(N² + N ×UniquePairs)।

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

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

class Solution {
public:
    int countTriplets(vector<int>& A) {
        unordered_map<int, int> m;
        int n = A.size();
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                m[A[i] & A[j]]++;
        
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int x = A[i];
            for (auto& p : m)
                if ((p.first & x) == 0)
                    ret += p.second;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,1,2};
    cout << ob.countTriplets(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {3,1,2}

আউটপুট: 12