HackerEarth Minimum addition problem solution

In this HackerEarth Minimum addition problem solution, You are given an array A[] of N positive numbers. You are also given Q queries. Each query contains two integers l,r (l <= r). For each query, determine the sum of all values that must be added to each number in range l to r such that bitwise AND of all numbers in the range is greater than 0.

You are required to minimize the total value that must be added. The value you must add to numbers is not necessarily equal for all numbers.

HackerEarth Minimum addition problem solution.

#include <bits/stdc++.h>
using namespace std;
#define int long long int
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=1000005;
#define M 1000000007
#define double long double
#define BINF 100000000000000
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 17500001
#define deb(x) cout << #x << " " << x << "\n";
const int LG = 22;

int p[32][N];
int a[N];
 
#undef int 
int main() {
#define int long long int
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("optput.txt", "w", stdout); 
#endif

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    for(int i = 0; i < 32; i++){
        for(int j = 1; j <= n; j++){
            if(a[j] & (1LL << i))
                p[i][j] = 1;
        }
    }
 
    for(int i = 0; i < 32; i++){
        for(int j = 1; j <= n; j++){
            p[i][j] += p[i][j - 1];
        }
    }
 
    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        int ans = 1e18;
        for(int i = 0; i < 32; i++){
            int set = (p[i][r] - p[i][l - 1]);
            ans = min(ans, (1LL << i) * (r - l + 1 - set));
        }
        cout << ans << endl;
    }
 
    
return 0;  
}

Second solution

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

const int maxn = 1e5 + 14, lg = 30;
int n;
ll cnt[maxn][lg];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        for(int j = 0; j < lg; j++)
            cnt[i + 1][j] = cnt[i][j] + max(0, (1 << j) - (x & (1 << j + 1) - 1));
    }
    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        l--;
        ll ans = LLONG_MAX;
        for(int i = 0; i < lg; i++)
            ans = min(ans, cnt[r][i] - cnt[l][i]);
        cout << ans << '\n';
    }
}