A bitwise pair

You are given an array $A$ of $N$ positive integers. Find the number of pairs $(i,j)$ such that:

• $(A[i]|A[j])-(A[i]\mathrm{\&}A[j])=(A[i]-A[j])$, where $|$ is a bitwise OR operator and $\mathrm{\&}$ is a bitwise AND operator.

Example:

Input: n = 4, arr = {4, 4, 2, 1}
Output: 6

Approach

Java

public class BitwisePair {
    public static void main(String[] args)  {
     
        int msk = 1024;
        int n = 4;
        int arr[] = { 4, 4, 2, 1 };
        int cnt[] = new int[msk];
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            int a = arr[i];
            ++cnt[a];
            mx = Math.max(mx, a);
        }
        long dp[] = new long[msk];
        for (int i = 0; i < msk; ++i)
            dp[i] = cnt[i];
        for (int i = 0; i < 11; ++i) {
            for (int j = 0; j < msk; ++j) {
                if ((j >> i & 1) != 0) {
                    dp[j] += dp[j ^ (1 << i)];
                }
            }
        }
        long ans = 0;
        for (int j = 0; j < msk; ++j) {
            ans += cnt[j] * dp[j];
        }
        System.out.println(ans);

    }
}

C++

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

int bitwisePair(int n, vector<int> arr)
{
    int msk = 1024;
    int cnt[msk];

    memset(cnt, 0, sizeof(cnt));
    int mx = 0;

    for (int i = 0; i < n; ++i)
    {
        int a = arr[i];
        ++cnt[a];
        mx = max(mx, a);
    }
    long dp[msk];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < msk; ++i)
        dp[i] = cnt[i];
    for (int i = 0; i < 11; ++i)
    {
        for (int j = 0; j < msk; ++j)
        {
            if ((j >> i & 1) != 0)
            {
                dp[j] += dp[j ^ (1 << i)];
            }
        }
    }
    long ans = 0;
    for (int j = 0; j < msk; ++j)
    {
        ans += cnt[j] * dp[j];
    }
    return ans;
}
int main()
{

    int n = 4;

    vector<int> arr = {4, 4, 2, 1};

    cout << bitwisePair(n, arr) << "\n";

    return 0;
}