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.

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

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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("%lld\n",ans);
    }

}

{"mode":"full","isActive":false}

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("%lld\n",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];
}

{"mode":"full","isActive":false}