Absolute Element Sums

  • + 0 comments

    Solution in Python

    def playingWithNumbers(arr, queries):
        A = arr
        Q = queries
        A.sort()
        final = []
        CumSum = [A[0]]
        for i in A[1:]:
            CumSum.append(i + CumSum[-1])
        SumAbs = sum([abs(m) for m in A])
        AddFactor = 0
        n = len(A)
        for I, i in enumerate(Q):
            AddFactor += i
            if AddFactor > 0:
                SplitLoc1 = bisect.bisect_right(A, -AddFactor)
                SplitLoc2 = bisect.bisect_left(A, 0)
                Mult = 1
            elif AddFactor < 0:
                SplitLoc2 = bisect.bisect_left(A, -AddFactor)
                SplitLoc1 = bisect.bisect_right(A, 0)
                Mult = -1
            elif AddFactor == 0:
                SplitLoc1 = -1
            if SplitLoc1 == -1:
                final.append(SumAbs)
            else:
                if SplitLoc1 == 0:
                    CSLeft = 0
                else:
                    CSLeft = CumSum[SplitLoc1 - 1]
                MiddleChange = Mult * ((SplitLoc2 - SplitLoc1) * AddFactor + 2 * (CumSum[max([0, SplitLoc2 - 1])] - CSLeft))
                LeftChange = -AddFactor * SplitLoc1
                RightChange = AddFactor * max([0, n - SplitLoc2])
                TotalChange = LeftChange + MiddleChange + RightChange
                Output = SumAbs + TotalChange
                final.append(Output)
        return final