Search code examples
pythonalgorithmsearchbinary-searchbisect

Absolute Elements Sums

I was trying to solve this problem on Hackerrank. https://www.hackerrank.com/challenges/playing-with-numbers/problem

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

  • Add x 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.

Can someone explain this solution to me?
I didn't quite understand the need to search for -q in the array n = bisect_left(arr, -q) and this line (Sc[-1] - 2 * Sc[n] + q * (N - 2 * n). 

from bisect import bisect_left
def playingWithNumbers(arr, queries):
    N = len(arr)
    res = []

    # Calculate cummulative sum of arr
    arr = sorted(arr)
    Sc = [0]
    for x in arr:
        Sc.append(x+Sc[-1])

    q = 0
    for x in queries:
        q += x
        n = bisect_left(arr, -q)
        res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n)))
    return res

Thank you

Solution

  • it's actually one of the solutions from the leaderboard. I tried running this code, but didn't fully understand why they used those terms and the idea of the code

    Okay, I see this now... It's a "smartass" way of calculating it. I actually thought about this idea when I read the task but I didn't thought of the specifics.

    Idea is: When you add x to each element, that element's absolute value changes by at most x - drops when you add to negative/subtract from positive, rises when you add to positive/subtracts from negative.

    Having a cumulative sum of a sorted list allows you to not go through the list each time and add, and sum, but to just calculate the value.

    Let's analyse it by taking the example input from the site:

    3
-1 2 -3
3
1 -2 3

    Our function gets: arr = [-1, 2, -3]; queries = [1, -2, 3]

    After sorting into arr = [-3, -1, 2] (let's say those are a,b,c - letters are better at explaining why this works) we get our cumulative sum Sc = [0, -3, -4, -2] (0, a, a+b, a+b+c).

    Now starts the smarty-pants part:

    -q is where our values turn over in the arr - that is, where adding q would go over 0, making the absolute value rise, instead of drop

    Let's translate this res.append((Sc[-1] - 2 * Sc[n] + q * (N - 2 * n))) one-by-one:

    1. Sc[-1] is the sum (a+b+c)
    2. let's take q*N first, it's how the whole sum changed when adding q (all x values up to this point) to each element
    3. Let's take - 2 * Sc[n] and q * (-2*n) together: -2 * (Sc[n] + q*n) - this is the turnover point I mentioned - if we have a negative number (we looked up -q, but we add q to it), neg - 2*abs(neg) = abs(neg), we use Sc and *n to turn over all the negative values.

    This solution's complexity is O(max(n,m)*logn) - because of the sorting. The cumulative sum thing is O(n), the smart loop is O(m*logn) (bisection is O(logn), I forgot it in the comment).

    Naive method with changing the values in the list would be O(n*m) - m times going through n-length list.