HackerRank Angry Children 2 problem solution

In this HackerRank Angry Children, 2 problem-solution Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has brought a box of packets of candies and would like to distribute one packet to each of the children.

Each of the packets contains a number of candies. He wants to minimize the cumulative difference in the number of candies in the packets he hands out. This is called the unfairness sum. Determine the minimum unfairness sum achievable.

HackerRank Angry Children 2 problem solution in Python.

# Elements are sorted
# x[k - 1] is larger than all other k - 1 elements,
# it occurs with a factor of (k - 1)
# x[k - 2] is larger than k - 2 elements but smaller than one
# it occurs with a factor of +(k - 2) and -1

# So in general, i occurs with a factor of +i and -(k - 1 - i)
def calc_angry_val(arr, start, k):
    angry_val = 0
    for i in range(k):
        angry_val = angry_val + nrs[start + i] * i - nrs[start + i] * (k - 1 - i)
    return angry_val

n = int(input())
k = int(input())

nrs = sorted(int(input()) for _ in range(n))

sums = [0] * (n + 1)
for i in range(n):
    sums[i + 1] = sums[i] + nrs[i]

# Let's select the first block of k candies and compute the angry_val
angry_val = calc_angry_val(nrs, 0, k)
result = angry_val

# Now if we proceed, shifting out the left value x_left removes (k - 1) * x_left
# And shifting in the new value x_right adds (k - 1) * x_right
for i in range(k, n):
    angry_val += (k - 1)  * nrs[i - k]
    angry_val += (k - 1)  * nrs[i]
    angry_val -= 2 * (sums[i] - sums[i - k + 1])
    result = min(result, angry_val)

print(result)

Angry Children 2 problem solution in Java.

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

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        long[] packets = new long[n];
        
        for (int i = 0; i < n; ++i) {
            packets[i] = sc.nextLong();
        }
        
        Arrays.sort(packets);
        
        long[] antisums = new long[n];
        
        for (int i = n - 2; i >= 0; i--) {
            if (i >= n - k) {
                antisums[i] = antisums[i + 1] + (n - 1 - i) * (packets[i + 1] - packets[i]);
            } else {
                antisums[i] = antisums[i + 1] - (packets[i + k] - packets[i + 1]) 
                    + (k - 1) * (packets[i + 1] - packets[i]);
            }
            
            
        }
        
        long[] sums = new long[n];
        long[] results = new long[n];
        long min = Long.MAX_VALUE;
        for (int i = 1; i <= n - 1; ++i) {   
            if (i <= k - 1) {
                sums[i] = sums[i - 1] + i * (packets[i] - packets[i - 1]);
                results[i] = results[i - 1] + sums[i];
            } else {
                sums[i] = sums[i - 1] - (packets[i - 1] - packets[i - k]) 
                    + (k - 1) * (packets[i] - packets[i - 1]);
                results[i] = results[i - 1] - antisums[i - k] + sums[i];  
            }
            
            if (i >= k - 1) {
                if (results[i] < min) {
                    min = results[i];
                }
            }
        }
        
        
        
        System.out.println(min);
    }
}

Problem solution in C++.

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

#define scani(a) scanf("%d",&a);
#define fori(a, b) for(i = a; i <= b; i++)
#define ll(a) (long long int)(a)
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n, k, i;
    scani(n)
    scani(k)
    int arr[n];
    long long int min, uf, ufn;
    fori(0, n-1)
        scani(arr[i])
    sort(arr, arr+n);
    long long int sum[n];
    sum[0] = ll(arr[0]);
    fori(1, n-1)
        sum[i] = ll(arr[i]) + sum[i-1];
    uf = 0LL;
    fori(0, k-2)
        uf += (sum[k-1] - sum[i]) - ll(arr[i]) * ll(k-i-1);
    min = uf;
    fori(1, n-k)
    {
        ufn = uf - ((sum[i-1+k-1] - sum[i-1]) - ll(arr[i-1]) * ll(k-1)) + (ll(k-1) * ll(arr[i+k-1]) - (sum[i+k-2] - sum[i-1]));
        if(ufn < min)
            min = ufn;
        uf = ufn;
    }
    printf("%lldn", min);
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
unsigned long long int a[100001];
int cmp(const void *a,const void *b)
{
    return (*(unsigned long long int*)a-*(unsigned long long int*)b);
}
int main() {
    int i,n,k,temp,j,l;
    unsigned long long int t,val,min;
    scanf("%d",&n);
    scanf("%d",&k);
    for(i=0;i<n;i++)
    scanf("%llu",a+i);
    qsort(a,n,sizeof(a[0]),cmp);
    min=0;
    temp=k;
    for(i=0,j=k-1;i<j;j--,i++)
    {
        min+=(temp-1)*(a[j]-a[i]);
        temp=temp-2;
    }
    for(i=1;i<=n-k;i++)
    {     
         // printf("NOn");
          temp=k;
          val=0;
         for(l=i,j=l+k-1;l<j;j--,l++)
         {   
             if(val<min)
             {
             val+=(temp-1)*(a[j]-a[l]);
             temp=temp-2;
             }
             else
                 break;

         }
        if(!min)
            break;
     if(val<min)
         min=val;
    }
    printf("%llun",min);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}