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
7
3
10
100
300
200
1000
20
30
Sample Output 0
40
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
10
4
1
2
3
4
10
20
30
40
100
200
Sample Output 1
10
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)