HackerRank Absolute Element Sums Problem Solution

HackerRank Absolute Element Sums Solution

Yashwant Parihar,

In this post, we will solve HackerRank Absolute Element Sums Problem Solution.

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:

  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.

Function Description

Complete the playingWithNumbers function in the editor below. It should return an array of integers that represent the responses to each query.

playingWithNumbers has the following parameter(s):

  • arr: an array of integers
  • queries: an array of integers

Input Format
The first line contains an integer n the number of elements in arr.
The second line contains n space-separated integers arr[i].
The third line contains an integer q, the number of queries.
The fourth line contains a space-separated integers a where queries[j] = x.

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: [1, 2, 3] → [0, 3, 2]
The sum of the absolute values of the updated array’s elements is
0+3+2=0+3+2=5.
Query 1:x=-2
Array: [0, 3, -2] → [2, 1, 4]
The sum of the absolute values of the updated array’s elements is
| 2+1+4 = 2+1+4 = 7.
Query 2: x = 3
Array: [2, 1, -4] → [1, 4, −1]
The sum of the absolute values of the updated array’s elements is
|1 + 4 + − 1 =1+4+1 = 6.

HackerRank Absolute Element Sums Problem Solution
HackerRank Absolute Element Sums Problem Solution

Absolute Element Sums C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long abssum(int * list, long offset, int pos, int psum, int neg, int nsum){
   long abssum = 0;

   if (offset > 0){
      for (int i = 0; i <= 2000; i++){
         abssum += abs(list[i]*(offset - 2000 + i));
      }
      abssum += offset*pos + psum;
   }
   else {
      for (int i = 2000; i <= 4000; i++){
         abssum += abs(list[i]*(offset - 2000 + i));
      }
      abssum -= offset*neg + nsum;
   }
   return abssum;
}

int main (void) {
   // get size of list
   int n;
   scanf("%d\n", &n);

   // get list
   int Ai = 0;
   int list[4001];
   int pos = 0;
   int psum = 0;
   int neg = 0;
   int nsum = 0;
   memset(list, 0, sizeof(int)*4001);
   for (int i = 0; i < n; i++){
      scanf("%d ", &Ai);
      list[2000+Ai]++;
      if (Ai > 0){
         pos++;
         psum += Ai;
      }
      if (Ai < 0){
         neg++;
         nsum += Ai;
      }
   }

   // get and process the queries
   int q;
   int x;
   int offset = 0;
   long abs = 0;

   scanf("%d\n", &q);
   for (int i = 0; i < q; i++){
      scanf("%d ", &x);
      offset += x;
      abs = abssum(list, offset, pos, psum, neg, nsum);
      fprintf(stdout, "%ld\n", abs);
   }

   return 0;
}

Absolute Element Sums C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


int bsearchGEIx(vector< long long > &vals, long long target)
{
    vector< long long >::iterator it = lower_bound(vals.begin(), vals.end(), target);
    if(it == vals.end()) { return vals.size(); }
    
    return it - vals.begin();
}

void computePrefixSums(vector< long long > &vals, vector< long long > &prefixSums)
{
    int n = vals.size();
    prefixSums.push_back(0);
    long long sum = 0;
    for(int len = 1;len <= n;len++)
    {
        int i = len - 1;
        sum += abs(vals[i]);
        prefixSums.push_back(sum);
    }
}

long long getOriginalAbsSum(vector< long long > &prefixSums, int startIx, int endIx)
{
    int len = endIx + 1;
    return prefixSums[len] - prefixSums[startIx];
}

long long getAbsSumPos(long long xSum, int geZeroIx, vector< long long > &vals, vector< long long > &prefixSums)
{
    int n = vals.size();
    long long negXSum = -xSum;
    int ix = bsearchGEIx(vals, negXSum);
    
    long long absSum1 = getOriginalAbsSum(prefixSums, 0, ix - 1) - ix * xSum;
    
    long long num2 = geZeroIx - ix;
    long long absSum2 = num2 * xSum - getOriginalAbsSum(prefixSums, ix, geZeroIx - 1);
    
    long long num3 = n - geZeroIx;
    long long absSum3 = getOriginalAbsSum(prefixSums, geZeroIx, n - 1) + num3 * xSum;
    
    return absSum1 + absSum2 + absSum3;
}

long long getAbsSumNeg(long long xSum, int geZeroIx, vector< long long > &vals, vector< long long > &prefixSums)
{
    int n = vals.size();
    long long negXSum = -xSum;
    int ix = bsearchGEIx(vals, negXSum);
    
    long long num1 = n - ix;
    long long absSum1 = getOriginalAbsSum(prefixSums, ix, n - 1) - num1 * negXSum;
    
    long long num2 = ix - geZeroIx;
    long long absSum2 = num2 * negXSum - getOriginalAbsSum(prefixSums, geZeroIx, ix - 1);
    
    long long absSum3 = getOriginalAbsSum(prefixSums, 0, geZeroIx - 1) + geZeroIx * negXSum;
    
    return absSum1 + absSum2 + absSum3;
}


int main()
{
    int N;
    cin >> N;
    vector< long long > vals;
    long long val;
    for(int i = 0;i != N;i++)
    {
        cin >> val;
        vals.push_back(val);
    }
    
    sort(vals.begin(), vals.end());
    int geZeroIx = bsearchGEIx(vals, 0);
    vector< long long > prefixSums;
    computePrefixSums(vals, prefixSums);
    
    int Q;
    cin >> Q;
    int x;
    long long xSum = 0;
    while(Q--)
    {
        cin >> x;
        xSum += x;
        
        if(xSum > 0) { cout << getAbsSumPos(xSum, geZeroIx, vals, prefixSums); }
        else if(xSum == 0) { cout << getOriginalAbsSum(prefixSums, 0, N - 1); }
        else { cout << getAbsSumNeg(xSum, geZeroIx, vals, prefixSums); }
        cout << endl;
    }
    
    return 0;
}

Absolute Element Sums C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution {

    class PlayingArray
    {
        private long[] array;
        public PlayingArray(int size)
        {
            Size = size;
            array = new long[Size * 2 + 1];
        }

        public int Size { get; private set; }

        public int Min { get { return -1 * Size; } }

        public int Max { get { return Size; } }

        public long this[int index]
        {
            get { return array[index + Size]; }
            set { array[index + Size] = value; }
        }
    }

    // Complete the playingWithNumbers function below.
    static long[] playingWithNumbers(int[] arr, int[] queries)
    {
        var length = arr.Length;
        
        // Sort input first;
        Array.Sort(arr);

        var initAbsoluteSum = (long) arr.Sum(item => Math.Abs(item));

        var firstZeroPos = Array.BinarySearch(arr, 0);
        if (firstZeroPos < 0)
        {
            firstZeroPos = ~firstZeroPos;
        }

        var playingArray = new PlayingArray(2000);
        var minQuery = -1 * arr[length - 1];
        var maxQuery = -1 * arr[0];
        var positivePos = firstZeroPos;
        var negativePos = firstZeroPos;

        for (var query = minQuery; query <= maxQuery; query++)
        {
            long add = 0;
            long subtract = 0;

            if (query > 0)
            {
                add = query;
                for (var index = negativePos - 1; index >= 0; index--)
                {
                    long number = -1 * arr[index];
                    if (add < number)
                    {
                        subtract += add * (index + 1);
                        break;
                    }
                    subtract += number;
                }
            }
            else
            {
                add = -1 * query;
                for (var index = positivePos; index < length; index++)
                {
                    long number = arr[index];
                    if (add < number)
                    {
                        subtract += add * (length - index);
                        break;
                    }
                    subtract += number;
                }
            }

            var absoluteSum = initAbsoluteSum + (add * length) - (subtract * 2);
            
            playingArray[query] = absoluteSum;
        }


        var effectiveQuery = 0;
        var absoluteSums = new List<long>();

        var minAbsoluteSum = playingArray[minQuery];
        var maxAbsoluteSum = playingArray[maxQuery];
        foreach (var query in queries)
        {
            effectiveQuery += query;

            long absoluteSum = 0;
            if (effectiveQuery < minQuery)
            {
                absoluteSum = minAbsoluteSum + ((long)length * (minQuery - effectiveQuery));
            }
            else if (effectiveQuery > maxQuery)
            {
                absoluteSum = maxAbsoluteSum + ((long)length * (effectiveQuery - maxQuery));
            }
            else
            {
                absoluteSum = playingArray[effectiveQuery];
            }

            if (absoluteSum < 0)
            {
                Console.WriteLine($"Negative Result!!! - Query:{query} EffectiveQuery: {effectiveQuery} AbsoluteSum:{absoluteSum}");
                System.Environment.Exit(-1);
            }

            absoluteSums.Add(absoluteSum);
        }

        return absoluteSums.ToArray();
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine());

        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp))
        ;
        int q = Convert.ToInt32(Console.ReadLine());

        int[] queries = Array.ConvertAll(Console.ReadLine().Split(' '), queriesTemp => Convert.ToInt32(queriesTemp))
        ;
        long[] result = playingWithNumbers(arr, queries);

        textWriter.WriteLine(string.Join("\n", result));

        textWriter.Flush();
        textWriter.Close();
    }
}

Absolute Element Sums Java Solution

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] A = new int[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            A[i] = in.nextInt();
            sum += A[i];
        }
        Arrays.sort(A);

        int q = in.nextInt();
        long[] values = new long[q];
        long last = 0;
        for (int i = 0; i < q; i++) {
            values[i] = in.nextInt() + last;
            last = values[i];
        }

        for (int i = 0; i < q; i++) {
            if (values[i] >= 0) {
                long neg = 0;
                int index = -1;
                for (int j = 0; A[j] * -1 > values[i]; j++) {
                    neg += A[j];
                    index = j;
                }
                long res = (values[i] * (index + 1) + neg) * -1 + (values[i] * (n - index - 1) + sum - neg);
                System.out.println(res);
            }
            else {
                long pos = 0;
                int index = n;
                for (int j = n - 1; A[j] * -1 < values[i]; j--) {
                    pos += A[j];
                    index = j;
                }
                long res = (values[i] * (n - index) + pos) + (values[i] * index + sum - pos) * -1;
                System.out.println(res);
            }
        }
    }
    
}

Absolute Element Sums JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'playingWithNumbers' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY arr
 *  2. INTEGER_ARRAY queries
 */

function playingWithNumbers1(arr, queries) {
    let xx = 0;
    return queries.map(x => {
        xx += x;
        return arr.reduce((acc, n) => acc + Math.abs(n+xx), 0);
    });
}
function playingWithNumbers2(arr, queries) {
    let sum = 0;
    let other = new Map();
    arr.forEach(n => {
        if (n < -2000 || n > 2000) {
            sum += Math.abs(n);
        }
        else {
            other.set(n, (other.get(n) || 0) + 1);
        }
    });
    let xx = 0;
    return queries.map(x => {
        xx += x;
        return [...other].reduce((acc, [n, c]) => acc + Math.abs(n+xx)*c, sum);
    });
}
function playingWithNumbers3(arr, queries) {
    let sum = 0;
    let other = [];
    arr.forEach(n => {
        if (n < -2000 || n > 2000) {
            sum += Math.abs(n);
        }
        else {
            other[n+2000] = (other[n+2000] || 0) + 1;
        }
    });
    let xx = 0;
    return queries.map(x => {
        xx += x;
        return other.reduce((acc, c, n) => acc + Math.abs(n-2000+xx)*c, sum);
    });
}
function playingWithNumbers(arr, queries) {
    return playingWithNumbers3(...arguments);
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine().trim(), 10);

    const arr = readLine().replace(/\s+$/g, '').split(' ').map(arrTemp => parseInt(arrTemp, 10));

    const q = parseInt(readLine().trim(), 10);

    const queries = readLine().replace(/\s+$/g, '').split(' ').map(queriesTemp => parseInt(queriesTemp, 10));

    const result = playingWithNumbers(arr, queries);

    ws.write(result.join('\n') + '\n');

    ws.end();
}

Absolute Element Sums Python Solution

import bisect

n = int(input().strip())
A = [int(m) for m in input().strip().split()]
input()
Q = [int(m) for m in input().strip().split()]

A.sort()
CumSum = [A[0]]
for i in A[1:]:
    CumSum.append(i + CumSum[-1])
SumAbs = sum([abs(m) for m in A])

AddFactor = 0
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:
        print(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
        print(Output)
c C# C++ HackerRank Solutions java javascript python

Leave a Reply