AND choice

M is alone and he has an array $a_1,a_2,...,a_n$. M wants to choose two integers $i,j$ such that $i\ne j,1\le i,j\le n$ and the value $a_i\mathrm{\&}{a}_j$ is maximum.

What is the maximum value M can get?

Example:

Input: n=4,arr = { 3, 4, 2, 3 }
Output: 3

Approach

Java

public class ANDChoice {
    public static void main(String[] args) {
        int n = 4;
        long[] arr = { 3, 4, 2, 3 };
        int ans = 0;
        for (int i = 31; i >= 0; --i) {
            int temp = ans | (1 << i);
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if ((temp & arr[j]) == temp) {
                    cnt++;
                }
            }

            if (cnt >= 2) {
                ans = ans | (1 << i);
            }
        }
        System.out.println(ans);
    }
}

A XOR value

You are given an array $A$ consisting of $N$ integer values. Find an integer $K$ such that the value of the following function is minimized:

• $\sum _{i=1}^{i=N}(A[i]XORK)$ , $XOR$ represents a bitwise XOR operation

If multiple such $K$ exist, then print the minimum possible value of $K$.

Example:

Input:  N=4, a[]={1,4,4,4}
Output: 4

Approach

Java

public class XORValue {
    public static void main(String args[]) {
        int N = 4;

        int a[] = { 1, 4, 4, 4 };

        int[] countbit = new int[64];
        for (int i = 0; i < N; i++) {
            long v = a[i];
            int idx = 0;
            while (v != 0) {
                countbit[idx] = countbit[idx] + (int) (v % 2);
                v = v / 2;
                idx++;
            }
        }
        long val = 0;
        for (int i = 63; i >= 0; i--) {
            val = 2 * val;
            if (2 * countbit[i] > N) {
                val = val + 1;
            }
        }
        System.out.println(val);
    }

}

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;
}