Bitwise AND sumBitwise AND sum solution

Rajnish Tripathi 15:22

 Problem

You are given an array � consisting of � positive integers. Here, �(�,�) is defined as the bitwise AND of all elements of the array � after replacing all elements of � in range [�,�] (both inclusive) with (225−1). Your task is to find:
                                                           −�(1,�)+∑�=1�∑�=���(�,�)

Note that after calculating the value �(�,�) for some (�,�), the array is restored back to its original form. Therefore, calculating �(�,�) for each (�,�) pair is independent.

You are given � test cases.

Warning: Use FAST I/O Methods.

Input format

  • The first line contains a single integer � denoting number of test cases.
  • For each test case:
    • The first line contains a single integer � denoting the length of the array.
    • The second line contains � space-separated integers denoting the integer array �.

Output format

For each test case, print the required sum in a separate line.

Constraints

1≤�≤10001≤�≤5×1050≤��<225Sum of N over all test cases does not exceed 106

Sample Input
2
3
3 4 1
2
4 2
Sample Output
5
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Consider the first test case, �=3, �=[3,4,1]. We want to evaluate �(1,1)+�(1,2)+�(2,2)+�(2,3)+�(3,3). Calculations are shown below:

  • �(1,1) : Replace �1 with (225−1), we get �=[33554431,4,1], Bitwise AND of elements is 0.
  • �(1,2) : Replace �1,�2 with (225−1), we get �=[33554431,33554431,1], Bitwise AND of elements is 1.
  • �(2,2) : Replace �2 with (225−1), we get �=[3,33554431,1], Bitwise AND of elements is 1.
  • �(2,3) : Replace �2,�3 with (225−1), we get �=[3,33554431,33554431], Bitwise AND of elements is 3.
  • �(3,3) : Replace �3 with (225−1), we get �=[3,4,33554431], Bitwise AND of elements is 0.
  • The sum is 0+1+1+3+0=5.

Consider the second test case, �=2, �=[4,2]. We want to evaluate �(1,1)+�(2,2). Calculations are shown below:

  • �(1,1) : Replace �1 with (225−1), we get �=[33554431,2], Bitwise AND of elements is 2.
  • �(2,2) : Replace �2 with (225−1), we get �=[4,33554431], Bitwise AND of elements is 4.
  • The sum is 2+4=6.

Bitwise AND sumBitwise AND sum Solution(C++):-


#include <iostream>
#include <vector>
#include <cstdint>
uint64_t bwand_sum(const std::vector<uint32_t> &v) {
constexpr uint32_t mask = (1 << 25) - 1;
const auto n = static_cast<int>(v.size());
int i, j;
std::vector<uint32_t> left_and(n + 1);
left_and[0] = mask;
for (i = 0; i < n; i++) {
left_and[i + 1] = v[i] & left_and[i];
}
std::vector<uint32_t> right_and(n);
right_and[n - 1] = mask;
for (i = n - 2; i >= 0; i--) {
right_and[i] = v[i + 1] & right_and[i + 1];
}
std::vector<int> ranges;
i = 0;
ranges.push_back(i);
while (i < n) {
for (j = i + 1;
j < n && left_and[i] == left_and[j] && right_and[i] == right_and[j];
j++) { }
i = j;
ranges.push_back(i);
}
const auto m = ranges.size();
uint64_t sum = 0u;
for (i = 0; i < m - 1; i++) {
const uint64_t len_i = ranges[i + 1] - ranges[i];
const uint64_t subrange_count_self = ((len_i + 1) * len_i) >> 1;
sum += subrange_count_self * static_cast<uint64_t>(left_and[ranges[i]] & right_and[ranges[i]]);
for (j = i + 1; j < m - 1; j++) {
const uint64_t len_j = ranges[j + 1] - ranges[j];
const uint64_t combined_range_count = len_i * len_j;
sum += combined_range_count * static_cast<uint64_t>(left_and[ranges[i]] & right_and[ranges[j]]);
}
}
return sum - mask;
}
int main(int argc, char **argv) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
while (t-- > 0) {
int n;
std::cin >> n;
std::vector<uint32_t> v(n);
for (auto i = 0; i < n; i++) {
std::cin >> v[i];
}
std::cout << bwand_sum(v) << '\n';
}
return 0;
}



Tags: