Minimum addition

You are given an array $A[]$ of $N$ positive numbers. You are also given $Q$ queries. Each query contains two integers $l,r(l\le 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.

Note: Each query is independent of each other, that is, for each query, you must treat the range over the initial input array.

Example:

Input:
5
4 3 2 4 1
4
1 4
2 3
4 4
4 5
Output : 
3
0
0
1

Approach

Java

public class MinimumAddition {
    private static final int NO_OF_BITS = 32;

    public static void main(String args[]) throws Exception {
        int n = 5;

        int arr[] = { 4, 3, 2, 4, 1 };
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = arr[i - 1];
        }
      
        long[][] prefixSumAddVal = new long[n + 1][NO_OF_BITS];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 32; j++) {
                int bitVal = 1 << j;
                int val = 0;
                if ((a[i] & bitVal) == 0) {
                    int mask = bitVal - 1;
                    val = bitVal - (a[i] & mask);
                }
                prefixSumAddVal[i][j] = prefixSumAddVal[i - 1][j] + val;
            }
        }
        // total query
        int Arr2D[][] = { { 1, 4 }, { 2, 3 }, { 4, 4 }, { 4, 5 } };
        int q = 4;
        StringBuffer sb = new StringBuffer();
        int j = 0;
        while (q-- > 0) {
            int l = Arr2D[j][0];
            int r = Arr2D[j][1];
            j++;

            long minVal = Integer.MAX_VALUE;
            for (int i = 0; i < 32; i++) {
                minVal = Math.min(minVal, prefixSumAddVal[r][i] - prefixSumAddVal[l - 1][i]);
            }
            sb.append(minVal).append("\n");
        }
        System.out.print(sb);
    }

}