HackerRank Algebra – XOR love

Challenge: XOR love

Subdomeniu: Algebra (algebra)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464755021

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/xor-love/problem

Cerinta

Devendra loves the XOR operation very much which is denoted by $\wedge$ sign in most of the programming languages. He has a list $A$ of $N$ numbers and he wants to know the answers of $M$ queries. Each query will be denoted by three numbers i.e. $K,P,R$ .

For query $K,P \text{ and } R$, he has to print the value of the $KPRsum$ which can be described as given below. As the value of the $KPRsum$ can be large. So, print it modulus $(10^9 + 7)$.

$$ KPRsum = \sum_{i=P}^{R-1} \sum_{j=i+1}^{R} (K \oplus (A[i] \oplus A[j]) )$$

**Input Format**  
The first line contains an integer $N$, i.e., the number of the elements in the list. List is numbered from $1$ to $N$.  
Next line will contain $N$ space seperated integers.  
Third line will contain a number $M$ i.e. number of queries followed by $M$ lines each containing  integers $K,P \& R$.

**Output Format**  
Print $M$ lines, $i^{th}$ line will be answer of $i^{th}$ query. **Answer will be 0 in case of P=R.**

**Constraints**  
$1 \le N \le 10^5$  
$1 \le A[i] \le 10^6$  
$1 \le M \le 10^5$  
$0 \le K \le 10^6$  
$1 \le P \le R \le N$

**Sample Input**  

	3
    1 2 3
    2
    1 1 3
    2 1 3

    
**Sample Output**  

	5
    4

**Explanation**

For first query, it will will be $$(1 \oplus( 1 \oplus 2) ) + (1 \oplus( 1 \oplus 3) ) + (1 \oplus( 2 \oplus 3) )  =  5 $$

Cod sursa

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

static const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    const int B = 31; // safe for values up to 1e9+
    vector<vector<int>> pref(B, vector<int>(n + 1, 0));
    for (int b = 0; b < B; ++b) {
        for (int i = 1; i <= n; ++i) {
            pref[b][i] = pref[b][i - 1] + ((a[i] >> b) & 1);
        }
    }

    vector<long long> pow2(B, 1);
    for (int b = 1; b < B; ++b) pow2[b] = (pow2[b - 1] * 2LL) % MOD;

    int q;
    cin >> q;
    while (q--) {
        int k, l, r;
        cin >> k >> l >> r;
        long long len = r - l + 1;

        long long ans = 0;
        for (int b = 0; b < B; ++b) {
            long long ones = pref[b][r] - pref[b][l - 1];
            long long zeros = len - ones;

            long long pairs_one;
            if (((k >> b) & 1) == 0) {
                // Need A[i]^A[j] bit = 1 -> different bits.
                pairs_one = ones * zeros;
            } else {
                // Need A[i]^A[j] bit = 0 -> same bits.
                pairs_one = ones * (ones - 1) / 2 + zeros * (zeros - 1) / 2;
            }

            long long contrib = (pairs_one % MOD) * pow2[b] % MOD;
            ans += contrib;
            if (ans >= MOD) ans -= MOD;
        }

        cout << ans % MOD << '\n';
    }

    return 0;
}