Table of Contents
Absolute Element Sums – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Absolute Element Sums HackerRank Solution
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
int main() {
int N;
scanf("%d", &N);
vector<long long> A(N);
rep(i, N) scanf("%lld", &A[i]);
sort(all(A));
vector<long long> sum(N+1, 0);
rep(i, N)
sum[i+1] = sum[i] + A[i];
int Q;
scanf("%d", &Q);
long long added = 0;
rep(ii, Q) {
int x;
scanf("%d", &x);
added += x;
//A[i] + added >= 0
//A[i] >= -added
int k = lower_bound(all(A), -added) - A.begin();
long long ans = 0;
ans += (sum[N] - sum[k]) + added * (N - k);
ans += -((sum[k] - sum[0]) + added * k);
printf("%lld\n", ans);
}
return 0;
}
Java Absolute Element Sums HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class C {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni();
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = ni();
Arrays.sort(a);
long[] cum =new long[n+1];
for(int i = 0;i < n;i++){
cum[i+1] = cum[i] + a[i];
}
long h = 0;
for(int Q = ni();Q >= 1;Q--){
int x = ni();
h -= x;
int ind = Arrays.binarySearch(a, h);
if(ind < 0)ind = -ind-2;
long ret = 0;
ret += cum[n]-cum[ind+1]-h*(n-(ind+1));
ret += -cum[ind+1]+h*(ind+1);
out.println(ret);
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Absolute Element Sums HackerRank Solution
from collections import Counter
def q(arr, queries):
positive_n = [el for el in arr if el >= 0]
negative_n = [el for el in arr if el < 0]
pos_size = len(positive_n)
neg_size = len(negative_n)
positive = list(reversed(sorted(Counter(positive_n).items())))
negative = sorted(Counter(negative_n).items())
tot = sum(abs(el) for el in arr)
diff = 0 # cum sum of queries
for q in queries:
diff += q
tot += pos_size * q - neg_size * q
if q > 0:
while neg_size and negative[-1][0] + diff >= 0:
(n, count) = negative.pop()
positive.append((n, count))
pos_size += count
neg_size -= count
tot += abs(n + diff) * 2 * count
else:
while pos_size and positive[-1][0] + diff < 0:
(n, count) = positive.pop()
negative.append((n, count))
neg_size += count
pos_size -= count
tot += abs(n + diff) * 2 * count
yield tot
input()
arr = [int(s) for s in input().split()]
input()
que = [int(s) for s in input().split()]
for res in q(arr, que):
print(res)
Python 2 Absolute Element Sums HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
input()
array = map(int, raw_input().split(" "))
input()
queries = map(int, raw_input().split(" "))
buckets = [0] * 4001
shift = 0
for i in array:
buckets[i + shift + 2000] += 1 # buckets from -2000 to 2000
for q in queries:
shift += q
if shift - q >= 2000 and shift >= 2000:
s += q * len(array)
elif shift - q <= -2000 and shift <= -2000:
s -= q * len(array)
else:
s = 0
for i, y in enumerate(buckets):
val = i + shift - 2000
s += y * abs(val)
print s
C Absolute Element Sums HackerRank Solution
#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];
}
Leave a comment below
