HackerRank Absolute Element Sums problem solution

In this HackerRank Absolute Element Sums problem solution, you have given an array of integers and a single integer x and we need to add x to each element of the array permanently modifying it for any future queries. and also 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

HackerRank Absolute Element Sums problem solution in Python.

n = int(input())
arr = list(map(int, input().split()))

q = int(input())
queries = list(map(int, input().split()))

count = [0]*4001
for i in arr:
    count[2000 + i] += 1
    
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
    sum_num_right.append(sum_num_right[i] - count[i])

sum_right = [0]*4001
for i in range(4001):
    sum_right[0] += count[i] * i
    
for i in range(1,4001):
    sum_right[i] = sum_right[i - 1] - sum_num_right[i]
    
sum_left = [0]*4001
for i in range(4000, -1, -1):
    sum_left[4000] += count[i] * (4000 - i)
    
for i in range(3999, -1, -1):
    sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
    
acc = 0
for i in queries:
    acc += i
    mid = 2000 - acc
    if mid < 4001 and mid >= 0:
        print(sum_right[mid] + sum_left[mid])
    elif mid < 0:
        print(sum_right[0] + n * abs(mid))
    else:
        print(sum_left[4000] + n * (mid - 4000))

Absolute Element Sums problem solution in Java.

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

Problem solution in C++.

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

int main()
{
	int n,query,x;
	long long ans=0,qsum=0;
    scanf("%d",&n);
	int a[n+1];
	long long sum[n+1];
	sum[0]=0;
    for(int i=1; i<=n; i++)
    {
     scanf("%d",&a[i]);
    }
    scanf("%d",&query);
    int en,st,mid;
    sort(a+1,a+n+1);
	for(int i=1; i<=n; i++)
	sum[i]=sum[i-1]+a[i];
    while(query--)
    {
        scanf("%d",&x);
        qsum+=x;
        st=0;
        en=n+1;
        while(en-st>1)
            {
                mid=(en+st)/2;
                if(a[mid]+qsum>=0) en=mid;
                else st=mid;
            }
            ans=-sum[en-1]-(en-1)*qsum+sum[n]-sum[en-1]+(n-en+1)*qsum;
            printf("%lldn",ans);
    }

}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
int a[500000],sum[500000];

int main(){
  int N,Q,offset=0,x,i;
  long long ans;
  scanf("%d",&N);
  for(i=0;i<N;i++)
    scanf("%d",a+i);
  sort_a(a,N);
  for(i=1,sum[0]=a[0];i<N;i++)
    sum[i]=sum[i-1]+a[i];
  scanf("%d",&Q);
  while(Q--){
    scanf("%d",&x);
    offset+=x;
    i=get_i(a,-offset+1,N);
    if(!i)
      ans=sum[N-1]+offset*(long long)N;
    else
      ans=sum[N-1]-2*sum[i-1]+offset*(long long)(N-2*i);
    printf("%lldn",ans);
  }
  return 0;
}
void sort_a(int*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
    int i = 0, j = 0;
    while (i < left_size|| j < right_size) {
        if (i == left_size) {
            a[i+j] = right[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}
int get_i(int*a,int num,int size){
  if(size==0)
    return 0;
  if(num>med(a,size))
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  else
    return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
  return a[(size-1)>>1];
}