Answer to Question #280530 in C++ for Rahul Sigh

Question

You have given an array A containing N integers. You can do the following operation at most K times:

•  Choose any index i and increase the value of At by 1.

Your task is to find the maximum bitwise OR of the array.

Input format

•  The first line contains an integer T denoting the number of test cases.

•  The first line of each test case contains two space-separated integers N and K.

•  The second line of each test case contains N space-separated integers denoting array A.

Output format

For each test case, print the maximum possible bitwise OR of the array after performing at most K operations in a new line.

Constraints

1 ≤ T ≤ 100000 1 ≤ N ≤ 200000

O ≤ K ≤ le18

O ≤ Ai ≤ 2⁶⁰

It is guaranteed that the sum of N over T test cases does not exceed le6.

Explanation

For the first test case, we can increase the value of the 5-th index by 2. Thus the A becomes {1, 3, 7, 0, 8, 1}. The bitwise OR of array A becomes 15.

Answer 1

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

int minSum(int a[], int n, int k)
{
    priority_queue <int> q;
     
    
    for(int i = 0; i < n; i++)
    {
        q.push(a[i]);
    }
     
    while(!q.empty() && k > 0)
    {
        int top = q.top() / 2;
         
        
        q.pop();
         
        
        q.push(top);
        k -= 1;
    }
     
    
    int sum = 0;
    while(!q.empty())
    {
        sum += q.top();
        q.pop();
    }
    return sum;
}
 

int main()
{
    int n = 4;
    int k = 3;
    int a[] = { 20, 7, 5, 4 };
         
    cout << (minSum(a, n, k));
     
    return 0;
}