# Absolute element sums challenge

**Problem statement**

Given an array, , of integers, you must answer queries. Each query consists of a single integer, , and is performed as follows:

- Add to each element of the array, permanently modifying it for any future queries.
- 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, (the number of elements in array ).

The second line contains space-separated integers describing each element in array .

The third line contains (the number of queries).

The fourth line contains space-separated integers (describing each ).

**Constraints**

, where and is the array of size

, where

**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*:

Array:

The sum of the absolute values of the updated array’s elements is , so we print on a new line.

*Query 1*:

Array:

The sum of the absolute values of the updated array’s elements is , so we print on a new line.

*Query 2*:

Array:

The sum of the absolute values of the updated array’s elements is , so we print on a new line.

**Larger Sample Input**

Input

Output

**Solution**

An observation we can make is that adding 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 .

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 will suffice. Lets call this value which is computed as follows: for and . The value will be used in each iteration to calculate the final sum for each query by adding it to each element of the array . Since we are going to slice our array in segments, with each element within a segment contributing similarly when summed with , it suffices to compute ( 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 is negative(), then by adding it to the sum of elements we basically subtract it from the segment’s sum. For elements the absolute value of their sum increases with .

Example array: and .

The sum of , which is , **decreases** by , so the final sum of the segment is (the first is the size of the segment). For the elements that are , , their sum goes towards when summed with . This is because and . So by adding we make it () negative (in case is ) or *more* negative (in case is already ). Thus the absolute sum , **increases** by an additional , and becomes . Adding both absolute values of the sums together, , we get a total sum of .

**2** If is positive (), then by adding it to the sum of elements we **increase** this sum with . For elements , their absolute sum gets **decreased** with .

Example array: and .

The elements are with a sum of . Their sum gets **increased** by and becomes . For elements , their absolute sum gets **decreased** with (because we are adding something positive to a negative). Those elements are . Adding to the numbers still keeps negative, but increases it towards . Increasing a negative number while still keeping it below , decreases its absolute value. That is for (with an absolute value of ), becomes with an absolute value of .

So in summary we are going to slice our array in elements that are and elements . 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 for each query 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 running time since our key value are and .

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); } } } }