Sum of difference of a number to an array of numbers
algorithm, arrays, c++, data-structures
Solution
You can run multiple queries for sums of absolute differences in `O(log N)` if you add a preprocessing step which costs `O(N * log N)`.
Sort the array, then for each item in the array store the sum of all numbers that are smaller than or equal to the corresponding item. This can be done in `O(N * log N)` Now you have a pair of arrays that look like this:
2 4 6 8 10 // <<== Original data
2 6 12 20 30 // <<== Partial sums
In addition, store the total `T` of all numbers in the array.
Now you can get sums of absolute differences by running a binary search on the original array, and using the sums from the partial sums array to compute the answer: subtract the sum of all numbers to the left of the target `k` from the count of numbers to the left of the target times `k`, then subtract the count times `k` from the sum to the right of the number, and add the two numbers together. The partial sum of the numbers to the right of the number can be computed by subtracting the partial sum on the left from the total `T`.
For `k=3` binary search gets you to position `1`.
- Partial sum on the left is 2
- Count of items on the left is 1
- Partial sum on the right is (30-2)=28
- Count of items on the right is 4
- You compute (1*3-2) + (28-4*3) = 1 + 16 = 17
Problem
This is my problem. Given an array of integers and another integer `k`, find the sum of differences of each element of the array and `k`. For example if the array is `2, 4, 6, 8, 10` and `k` is `3` ``` Sum of difference = abs(2 - 3) + abs(4-3) + abs(6 - 3) + abs(8 - 3) + abs(10 - 3) = 1 + 1 + 3 + 5 + 7 = 17 ``` The array remains the same throughout and can contain up to 100000 elements and there will be 100000 different values of k to be tested. k may or may not be an element of the array. This has to be done within 1s or about 100M operations. How do I achieve this?