Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Absolute element sums challenge

Sharing is caring!

Problem statement
Given an array, A, of N integers, you must answer Q queries. Each query consists of a single integer, x, and is performed as follows:

  1. Add x to each element of the array, permanently modifying it for any future queries.
  2. Find the absolute value of each element in the array and print the sum of the absolute values on a new line.

Tip: The Input/Output for this challenge is very large, so you’ll have to be creative in your approach to pass all test cases.

Input Format
The first line contains an integer, N (the number of elements in array A).
The second line contains N space-separated integers describing each element i in array A.
The third line contains Q (the number of queries).
The fourth line contains Q space-separated integers (describing each x_j).

Constraints
1 \le N \le 5\times 10^5
1 \le Q \le 5\times 10^5
-2000 \le A[i] \le 2000, where 0 \le i \textless N and A is the array of size N
-2000 \le Ax_j \le 2000, where 0 \le j \textless Q

Output Format
For each query, print the sum of the absolute values of all the array’s elements on a new line.

Sample Input

3
-1 2 -3
3
1 -2 3 

Sample Output

5
7
6

Explanation
Query 0: x=1
Array: \left[-1,2,-3\right] \rightarrow \left[0,3,-2\right]
The sum of the absolute values of the updated array’s elements is |0| + |3| + |-2| = 0 + 3 +2 = 5, so we print 5 on a new line.

Query 1: x=-2
Array: \left[0,3,-2\right] \rightarrow \left[-2,1-4\right]
The sum of the absolute values of the updated array’s elements is |-2| + |1| + |-4| = 2 + 1 + 4 = 7, so we print 7 on a new line.

Query 2: x=3
Array: \left[-2,1-4\right] \rightarrow \left[1,4,-1\right]
The sum of the absolute values of the updated array’s elements is |1| + |4| + |-1| = 1 + 4 + 1 = 6, so we print 6 on a new line.

Larger Sample Input
Input
Output

Solution
An observation we can make is that adding x to positive or negative array elements will affect the resulting sum differently. So we need to find a way to slice our array in different segments depending on how they will contribute to the final sum when added together with x.

Another observation we can make is that we don’t have to iterate over the array for every query. Using the accumulated sum of the values x will suffice. Lets call this value add which is computed as follows: add_i = add_{i-1} + x_i for i>0 and add_0 = x_0. The value add will be used in each iteration to calculate the final sum for each query by adding it to each element A[i] of the array A. Since we are going to slice our array in segments, with each element within a segment contributing similarly when summed with add, it suffices to compute k\times add (k is the size of segment) in order to find out how much the sum of a segment increases/decreases.

On what criteria do we slice our array?
1 If add is negative(\textless 0), then by adding it to the sum of elements A[i] \ge -add we basically subtract it from the segment’s sum. For elements A[i] \textless -add the absolute value of their sum increases with add.

Example array: \left[-3, -1, 1, 2, 3\right] and add=-2.
The sum of \left[2,3\right], which is 5, decreases by 2\times(-2)=-4, so the final sum of the segment is 5 - 4 = 1 (the first 2 is the size of the segment). For the elements j that are \textless -add =2, \left[-3, -1, 1\right], their sum goes towards -\infty when summed with add \textless 0. This is because add\textless 0 and -add \textgreater j. So by adding add we make it (j) negative (in case j is \textgreater 0) or more negative (in case j is already \textless 0). Thus the absolute sum |-3|=3, increases by an additional |3\times -2|=|-6|=6, and becomes |-9| = 9. Adding both absolute values of the sums together, 1+9, we get a total sum of 10.

2 If add is positive (\textgreater 0), then by adding it to the sum of elements A[i]\ge -add we increase this sum with add. For elements A[i] \textless -add, their absolute sum gets decreased with add.

Example array: \left[-3, -1, 1, 2, 3\right] and add=1.
The elements \ge -add = -1 are \left[-1, 1, 2, 3\right] with a sum of 5. Their sum gets increased by 4\times 1 and becomes 9. For elements A[i] \textless -add = -1, their absolute sum gets decreased with add (because we are adding something positive to a negative). Those elements are \left[-3\right]. Adding add\textgreater 0 to the numbers A[i]\textless -add still keeps A[i] negative, but increases it towards +\infty. Increasing a negative number while still keeping it below 0, decreases its absolute value. That is for -3 (with an absolute value of 3), -3 + 1 becomes -2 with an absolute value of 2.

So in summary we are going to slice our array in elements that are \textless-add and elements \ge -add. This is easily done when the array is sorted.

We know that sorting the array will not affect the end result since the elements order is irrelevant when computing the sum. Once our array is sorted we can use Binary Search to find the start/end of the segments in our sorted array.

So lets go ahead and implement our binary search function:

/**
 * Returns an index pointing to the first element in the range [first, last]
 * that is greater or equal to value or -1 if no such element is found.
 */
private static int lowerBound(long[] a, int first, int last, long value) {
    if (first >= last) {
        if (a[first] >= value) {
            return first;
        } else {
            return -1;
        }
    } else {
        int mid = first + (last - first) / 2;
        if (a[mid] >= value) {
            // Element is found --> search leftward until you find a non-matching element.
            return lowerBound(a, first, mid, value);
        } else {
            return lowerBound(a, mid + 1, last, value);
        }
    }
}

Next, after we have read our array we are going to sort it:

// Sort array
Arrays.sort(a);

We will also use prefix sum to get the sum of each segment:

// Compute prefix sum
long[] prefixSum = new long[n];
prefixSum[0] = a[0];
for (int i = 1; i < n; i++) {
    prefixSum[i] = prefixSum[i - 1] + a[i];
}

Finally, for the main part we read the value x for each query q and compute our absolute sum:

long add = 0;
for (int q = 0; q < queries; q++) {
    long x = in.nextLong();

    add += x;
    
    int lo = lowerBound(a, 0, n - 1, -1 * add); // Segment separation index

    long ans = 0;
    if (lo > 0) {
        ans = Math.abs(prefixSum[lo - 1] + lo * add) + (prefixSum[n - 1] - prefixSum[lo - 1]) + (n - lo) * add;
    } else {
        ans = Math.abs(prefixSum[n - 1] + n * add);
    }

    long expected = out.nextLong();
    if (expected != ans) {
        System.out.println("Expected " + expected + " got " + ans);
    } else {
        System.out.println(ans);
    }
}

The full code is available below.

Full code

public class AbsoluteElementsSum {
    /**
     * Returns an index pointing to the first element in the range [first, last]
     * that is greater or equal to value or last if no such element is found.
     */
    private static int lowerBound(long[] a, int first, int last, long value) {
        if (first >= last) {
            if (a[first] >= value) {
                return first;
            } else {
                return -1;
            }
        } else {
            int mid = first + (last - first) / 2;
            if (a[mid] >= value) {
                // Element is found --> search leftward until you find a non-matching element.
                return lowerBound(a, first, mid, value);
            } else {
                return lowerBound(a, mid + 1, last, value);
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);
        Scanner out = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out.txt"));

        int n = in.nextInt();
        long[] a = new long[n];

        // Read input
        for (int i = 0; i < n; i++) {
            a[i] = in.nextLong();
        }

        // Sort array
        Arrays.sort(a);

        // Compute prefix sum
        long[] prefixSum = new long[n];
        prefixSum[0] = a[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + a[i];
        }

        int queries = in.nextInt();
        long add = 0;
        for (int q = 0; q < queries; q++) {
            long x = in.nextLong();

            add += x;

            int lo = lowerBound(a, 0, n - 1, -1 * add);

            long ans = 0;
            if (lo > 0) {
                ans = Math.abs(prefixSum[lo - 1] + lo * add) + (prefixSum[n - 1] - prefixSum[lo - 1]) + (n - lo) * add;
            } else {
                ans = Math.abs(prefixSum[n - 1] + n * add);
            }

            long expected = out.nextLong();
            if (expected != ans) {
                System.out.println("Expected " + expected + " got " + ans);
            } else {
                System.out.println(ans);
            }
        }
    }
}

In the code above we have used Arrays.sort(a) which uses Quicksort underneath. I have modified the code to use Counting sort for the sorting part which tends to have \mathcal{O}(n) running time since our key value are \le 2000 and \ge -2000.

public class AbsoluteElementsSum {
    private static final int MIN = -2000;
    private static final int MAX = 2000;

    private static int[] sort(int[] a) {
        final int OFFSET = Math.abs(MIN);
        int[] countLessEq = new int[2 * MAX + 2];
        int[] count = new int[2 * MAX + 2];

        int n = a.length;

        for (int i = 0; i < n; i++) {
            count[OFFSET + a[i]] = count[OFFSET + a[i]] + 1;
            countLessEq[OFFSET + a[i]] = countLessEq[OFFSET + a[i]] + 1;
        }

        for (int i = MIN + 1; i <= MAX; i++) {
            countLessEq[OFFSET + i] = countLessEq[OFFSET + i] + countLessEq[OFFSET + i - 1];
        }

        int[] position = new int[2 * MAX + 2];
        Arrays.fill(position, -1);
        for (int i = 0; i < n; i++) {
            if (position[OFFSET + a[i]] == -1) {
                position[OFFSET + a[i]] = countLessEq[OFFSET + a[i]] - count[OFFSET + a[i]];
            } else {
                position[OFFSET + a[i]] = position[OFFSET + a[i]] + 1;
            }
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int pos = position[OFFSET + a[i]] - count[OFFSET + a[i]] + 1;
            result[pos] = a[i];
            count[OFFSET + a[i]] = count[OFFSET + a[i]] - 1;
        }

        return result;
    }

    /**
     * Returns an index pointing to the first element in the range [first, last] that is greater or equal to value or
     * last if no such element is found.
     */
    private static int lowerBound(int[] a, int first, int last, long value) {
        if (first >= last) {
            if (a[first] >= value) {
                return first;
            } else {
                return -1;
            }
        } else {
            int mid = first + (last - first) / 2;
            if (a[mid] >= value) {
                // Element is found --> search leftward until you find a non-matching element.
                return lowerBound(a, first, mid, value);
            } else {
                return lowerBound(a, mid + 1, last, value);
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);
        Scanner out = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out.txt"));

        int n = in.nextInt();
        int[] a = new int[n];

        // Read input
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }

        // Sort array
        a = sort(a);

        // Compute prefix sum
        long[] prefixSum = new long[n];
        prefixSum[0] = a[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + a[i];
        }

        int queries = in.nextInt();
        long add = 0;
        for (int q = 0; q < queries; q++) {
            long x = in.nextLong();

            add += x;

            int lo = lowerBound(a, 0, n - 1, -1 * add);

            long ans = 0;
            if (lo > 0) {
                ans = Math.abs(prefixSum[lo - 1] + lo * add) + (prefixSum[n - 1] - prefixSum[lo - 1]) + (n - lo) * add;
            } else {
                ans = Math.abs(prefixSum[n - 1] + n * add);
            }

            long expected = out.nextLong();
            if (expected != ans) {
                System.out.println("Expected " + expected + " got " + ans);
            } else {
                System.out.println(ans);
            }
        }
    }
}