Given an array of integers Arr and an integer K, bitwise AND is to be performed on each element A[i] with an integer X

Let Final sum be defined as follows: Sum of ( A[i] AND X ) for all values of i ( 0 to length of array-1 )

Return the integer X subject to following constraints:

• Final sum should be maximum
• X should contain exactly K bits as 1 in its binary representation
• If multiple values of X satisfy the above conditions, return the minimum possible X

Input:
Arr : [8,4,2]
K = 2

Output: X=12

12 Contains exactly 2 bits in its binary and is the smallest number that gives maximum possible answer for
summation of all (A[i] AND X)

Approach Tried :

Took bitwise OR for all numbers in the array in binary and retained the first K bits of the binary that had 1 , made remaining bits 0, convert back to int

Passed 7/12 Test Cases

Can someone help me out with what mistake am I making with regards to the approach or suggest a better approach ? Thanks in advance.

CodePudding user response：

Consider an input like [ 8, 4, 4, 4 ], K = 1. Your algorithm will give 8 but the correct answer is 4. Just because a given bit is more significant doesn't mean that it will automatically contribute more to the sum, as there might be more than twice as many elements of the array that use a smaller bit.

My suggestion would be to compute a weight for each bit of your potential X -- the number of elements of the array that have that bit set times the value of that bit (2ⁱ for bit i). Then find the K bits with the largest weight.

To do this, you need to know how big your integers are -- if they are 32 bits, you need to compute just 32 weights. If they might be bigger you need more. Depending on your programming language you may also need to worry about overflow with your weight calculations (or with the sum calculation -- is this a true sum, or a sum mod 2ⁿ for some n?). If some elements of the array might be negative, how are negatives represented (2s complement?) and how does that interact with AND?

CodePudding user response：

Let dp[k][i] represent the maximum sum(a & X), a ∈ array, where i is the highest bit index in X and k is the number of bits in X. Then:

dp[1][i]:
  max(sum(a & 2^i))
    for i in word size
  
dp[k][i]:
  max(sum(a & 2^i)   max(dp[k-1][j]))
    for i in word size
        j < i

sum(a & 2^i) can be precalculated for all values of i in O(n * m), where m is the word size. max(dp[k-1][j]) is monotonically increasing over j and we want to store the earliest instance of each max to minimise the resulting X.

For each k, therefore, we iterate over m is. Overall time complexity O(k * m n * m), where m is the word size.