HackerRank Angry Children 2 Problem Solution

In this post, we will solve 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.

For example, he brings n = 7 packets where the number of candies is packets= [3, 3, 4, 5, 7, 9, 10]. There are k = 3 children. The minimum difference between all packets can be had with 3, 3, 4 from indices 0, 1 and 2. We must get the difference in the following pairs: {(0, 1), (0, 2), (1, 2)}. We calculate the unfairness sum
as:

packets candies				
0	3		indices		difference	result
1	3		(0,1),(0,2)	|3-3| + |3-4|	1 
2	4		(1,2)		|3-4|		1

Total = 2

Function Description

Complete the angryChildren function in the editor below. It should return an integer that represents the minimum unfairness sum achievable.

angryChildren has the following parameter(s):

k: an integer that represents the number of children
packets: an array of integers that represent the number of candies in each packet

Input Format

The first line contains an integer n.
The second line contains an integer k.
Each of the next n lines contains an integer packets[i].

Output Format

A single integer representing the minimum achievable unfairness sum.

Sample Input 0

Sample Output 0

Explanation 0

Bill Gates will choose packets having 10, 20 and 30 candies. The unfairness sum is |10 – 20| + |20 – 30| + |10 – 30| =40|

Sample Input 1

Sample Output 1

HackerRank Angry Children 2 Problem Solution

Table of Contents

Angry Children 2 C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAXSIZE 100000
int cmpfunc(const void *a,const void *b){
    return (*(long long int*)a - *(long long int*)b);
}
int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n,k,i,j,flag,count;
    long long int A[MAXSIZE],unfair,sum,min;
    scanf("%d %d",&n,&k);
    for(i=0;i<n;i++){
    scanf("%lld",&A[i]);
    }
    qsort(A,n,sizeof(long long int),cmpfunc);
    unfair=0;
    flag=k-1;
    count=1;
    for(i=1;i<k;i++){
    unfair+=flag*count*(A[i]-A[i-1]);
    flag--;
    count++;
    }
    sum=0;
    for(i=1;i<k;i++){
    sum+=A[i];
    }
    min=unfair;
    for(i=k;i<n;i++){
    unfair=unfair+(k-1)*(A[i]+A[i-k])-2*(sum);
    if(unfair<min){
    min=unfair;
    }
    sum+=(A[i]-A[i-k+1]);
    }
    printf("%lld\n",min);
    return 0;
}

Angry Children 2 C++ Solution

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


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    long long n,k;cin>>n>>k;
    vector<long long> a(n);
    for(int i=0;i<n;++i)cin>>a[i];
    sort(a.begin(),a.end());
    long long su=a[0];
    long long tmp=0;
    for(long long i=1;i<k;++i){
        tmp+=(a[i]*i-su);
        su+=a[i];
    }
    long long res=tmp;
    for(long long i=k;i<n;++i){
        tmp-=(su-a[i-k]*k);
        su-=a[i-k];
        tmp+=(a[i]*(k-1)-su);
        su+=a[i];
        res=min(tmp,res);
    }
    cout<<res<<endl;
    return 0;
}

Angry Children 2 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 {

    // Complete the angryChildren function below.
    static long angryChildren(int k, int[] packets, int n) {
        packets = packets.OrderBy(p => p).ToArray();
        long currRes = 0;
        long prevAdd = 0;
        for(var i = 1; i < k; ++i) {
            prevAdd += (packets[i] - packets[i-1]) * i;
            currRes += prevAdd;
        }
        long res = currRes;
        long prevSubstr = 0;
        for(var i = 1; i < k; ++i) {
            prevSubstr += packets[i] - packets[0];
        }
        for(var i = k; i < n; ++i) {
            currRes -= prevSubstr;
            prevSubstr -= ((long)(packets[i-k+1] - packets[i-k])) * (k-1);
            prevSubstr += packets[i] - packets[i-k+1];
            prevAdd -= packets[i - 1] - packets[i-k];
            prevAdd += ((long)(packets[i] - packets[i-1])) * (k-1);
            currRes += prevAdd;
            res = Math.Min(res, currRes);
        }
        return res;
    }

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

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

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

        int[] packets = new int [n];

        for (int i = 0; i < n; i++) {
            int packetsItem = Convert.ToInt32(Console.ReadLine());
            packets[i] = packetsItem;
        }

        long result = angryChildren(k, packets, n);

        textWriter.WriteLine(result);

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

Angry Children 2 Java Solution

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

Angry Children 2 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', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

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

function sortNumArrayAsc(array) {
  array.sort((a, b) => {
    return (a < b) ? -1 : ((a > b) ? 1 : 0)
  })
}

// Complete the angryChildren function below.
function angryChildren(k, packets) {
    sortNumArrayAsc(packets);
    packets = packets.map(el => BigInt(el));
    let i = 0, ufSum = BigInt(0), ufSumMin = BigInt(0), ufBody = BigInt(0), multiplier = BigInt(1 - k);
    for (true; i < k; i++) {
        ufSum += packets[i] * multiplier;
        multiplier += BigInt(2);
        if (i > 0) ufBody += packets[i];
    }
    ufSumMin = ufSum;
    for (true; i < packets.length; i++) {
        ufSum = ufSum + BigInt((k - 1)) * (packets[i] + packets[i - k]) - BigInt(2) * ufBody;            
        if (ufSum < ufSumMin) ufSumMin = ufSum;
        ufBody = ufBody + packets[i] - packets[i - k + 1];
    }
    return ufSumMin
}

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

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

    const k = parseInt(readLine(), 10);

    let packets = [];

    for (let i = 0; i < n; i++) {
        const packetsItem = parseInt(readLine(), 10);
        packets.push(packetsItem);
    }

    let result = angryChildren(k, packets);

    ws.write(result + "\n");

    ws.end();
}

Angry Children 2 Python Solution

#!/usr/bin/env python3

# https://www.hackerrank.com/challenges/angry-children-2

N = int(input())
K = int(input())

a = []
for i in range(0, N):
    a.append(int(input()))
a = sorted(a)

# if unfairness for i .. i + K == n_i, what is unfairness for
# i+1 .. i+K+1 = n_{i+1}?
# n_{i+1} = n{i} - \sum_{j=1}^{K-1}X_{i+j}-X_i + \sum_{j=1}^{K-1}X_{i+K}-X_{i+j}
# n_{i+1} = n{i} + (K-1)(X_i+X_{i+K}) - 2\sum_{j=1}^{K-1}X_{i+j}
# n{0} = -(K-1)X_0 + (-(K-2)+1)X_1 + (-(K-3)+2))X_2 + \dots

d = 0
s = 0
mul = -(K - 1)
for i in range(0, K):
    d += mul * a[i]
    mul += 2
    s += a[i]
s -= a[0]

min_d = d
for i in range(1, N - K):
    d = d + (K - 1) * (a[i - 1] + a[i - 1 + K]) - 2 * s
    min_d = min(min_d, d)
    s -= a[i]
    s += a[i + K - 1]

print(min_d)