Atlassian OA | SDE | 2023

Question

Answer 1

int getCurrentBit(int n, int bit)
{
    return ((n >> bit) & 1);
}

int findSumOfXORTriplets(int n, vector<int> &arr)
{
    /*
     * @param max_e maximum element in array
     * @param bits no of bits of max element in array
    */
    int max_e = *max_element(arr.begin(), arr.end());
    int bits = log2(max_e);
    int ans = 0;
    for (int i = bits; i >= 0; i--)
    {
        /*
         * Check for each bit, how many of the triplets can provide a value of XOR as 1 
         * add to no of 1 values multiplied by current bit value i.e 2^(i) or (1 << i)
        */
        int cnt0 = 0, cnt1 = 0;
        for (int x : arr)
        {
            int curr = getCurrentBit(x, i);
            cnt0 += (curr == 0);
            cnt1 += (curr == 1);
        }
        /*
         * @param n1 count of 1
         * @param n0 count of 0
         * For ith bit
            - case 1 : 1 0 0 = n1*n0*(n0-1) = n1C1*n0C2
            - case 2 : 1 1 1 = n1*(n1-1)*(n1-2) = n1C3
        */
        int curr_bit_value = (1 << i);
        int case1 = cnt1 * cnt0 * (cnt0 - 1) / 2;
        int case2 = cnt1 * (cnt1 - 1) * (cnt1 - 2) / 6;
        ans += (case1 + case2) * curr_bit_value;
    }
    return ans;
}