# Solving Angry Children 2 problem

Hacker rank problem

Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has **N** packets of candies and would like to distribute one packet to each of the **K** children in the village (each packet may contain different number of candies). To avoid a fight between the children, he would like to pick **K** out of **N** packets such that the unfairness is minimized.

Suppose the **K** packets have (x_{1}, x_{2}, x_{3},….x_{k}) candies in them, where x_{i} denotes the number of candies in the i^{th} packet, then we define *unfairness* as

where |a| denotes the absolute value of a.

**Input Format**

The first line contains an integer N.

The second line contains an integer K. N lines follow each integer containing the candy in the i^{th} packet.

**Output Format**

A single integer which will be minimum unfairness.

**Constraints**

2<=N<=10^{5}

2<=K<=N

0<= number of candies in each packet <=10^{9}

**Sample Input #00**

```
7
3
10
100
300
200
1000
20
30
```

**Sample Output #00**

```
40
```

**Explanation #00**

Bill Gates will choose packets having 10, 20 and 30 candies.So unfairness will be |10-20| + |20-30| + |10-30| = 40. It will be minimum as compared to any other distribution which can be verified .

**Sample Input #01**

```
10
4
1
2
3
4
10
20
30
40
100
200
```

**Sample Output #01**

```
10
```

**Explanation #01**

Bill Gates will choose 4 packets having 1,2,3 and 4 candies. So, unfairness will be |1-2| + |1-3| + |1-4| + |2-3| + |2-4| + |3-4| = 10

1) First attempt, which did not pass all the test cases:

package main

import (

“fmt”

“sort”

“math”

)func main() {

//Enter your code here. Read input from STDIN. Print output to STDOUT

var N int

fmt.Scan(&N)

var K int

fmt.Scan(&K)arr := make([]int, N)

for i:=0; i<N; i++ {

fmt.Scan(&arr[i])

}

sort.Ints(arr)

//fmt.Printf(“N: %v, K: %v\n”, N, K)

//fmt.Printf(“arr: %v\n”, arr)prev_sz_dp := make([]int, N)

// DP comes here in size

for sz:=2; sz<=K; sz++ {

for i:=0; i<=N-sz; i++ {

j:= i+sz-1

for k:=i; k<i+sz-1; k++ {

prev_sz_dp[i] += int(math.Abs(float64(arr[j] – arr[k])))

}

}

}//fmt.Printf(“prev_sz_dp: %v\n”, prev_sz_dp)

min:=-1

for i:=0; i<=N-K; i++ {

if min == -1 || min > prev_sz_dp[i] {

min = prev_sz_dp[i]

}

}fmt.Printf(“%v\n”, min)

}

2) Second attempt

I introduced some math bit as shown in the comment.

package main

import (

“fmt”

“sort”

“math”

)func main() {

//Enter your code here. Read input from STDIN. Print output to STDOUT

var N int

fmt.Scan(&N)

var K int

fmt.Scan(&K)arr := make([]int, N)

for i:=0; i<N; i++ {

fmt.Scan(&arr[i])

}

sort.Ints(arr)

//fmt.Printf(“N: %v, K: %v\n”, N, K)

// fmt.Printf(“arr: %v\n”, arr)//prev_sz_dp := make([]int, N)

// loop for the starting point of a K set, shifting by 1 to the right

minUnFairness := int64(-1)

for st:=0; st < N-K; st++ {

// Math bit

// I understand (after some thinking) that the formula to get the

// unfairness is

// unfairness = nl * diff * nr

// where nl is no. of elements on left side of an element in a given K set

// nr is no. of elements on the right side of the given element

// diff is the diff beween the given element and its prev (left) element)

unfairness := int64(0)

for i := st+1; i<st+K; i++ {

diff := int(math.Abs(float64(arr[i] – arr[i-1])))

unfairness += int64( (i-st) * diff * (st+K-i))

}

// fmt.Printf(“unfairness at %v : %v\n”, st, unfairness)

if minUnFairness == -1 || minUnFairness > unfairness {

minUnFairness = unfairness

}

}fmt.Printf(“%v\n”, minUnFairness)

}

Now 8 out of 15 pass. But 7 still time out.

I think I need to add some Dynamic programming (DP) bit.

Oh and I did not mention. I purchased a few test cases using hackos. Hackos are points which you have already earned by solving problems. And you can buy some more test cases other than those 2 provided as part of the problem to help improve your solution. Thereby making it pass more (ideally all) test cases.

3) Third attempt with trying to use more mathematics

and calculate the unfairness using avg of a K-1 set, and previously calculated unfairness. This should work the code listing below:

package main

import (

“fmt”

“sort”

“math”

)func main() {

//Enter your code here. Read input from STDIN. Print output to STDOUT

var N int

fmt.Scan(&N)

var K int

fmt.Scan(&K)arr1 := make([]int, N)

for i:=0; i<N; i++ {

fmt.Scan(&arr1[i])

}

sort.Ints(arr1)arr := make([]int64, N)

for i:=0; i<N; i++ {

arr[i] = int64(arr1[i])

}

// fmt.Printf(“N: %v, K: %v\n”, N, K)

// fmt.Printf(“arr: %v\n”, arr)//prev_sz_dp := make([]int, N)

lval := arr[0]

unfairness := float64(0)// compute the avg and unfairness of the first set

sum := float64(0)

for i:=1; i<K; i++{sum += float64(arr[i])

diff := int64(math.Abs(float64(arr[i] – arr[i-1])))

unfairness += float64( int64(i * (K-i)) * diff )

}

avg := sum / float64(K-1)// fmt.Printf(“unfairness: %v\n”, unfairness)

// fmt.Printf(“avg: %v\n”, avg)

minUnFairness := int64(unfairness)// loop for the all other k sets by shifting right

// but compute the unfairness optimally (i.e by using avg and left val)

for i:=K; i<N; i++ {

unfairness -= (avg – float64(lval) ) * float64(K-1)

unfairness += (float64(arr[i]) – avg) * float64(K-1)

// fmt.Printf(“unfairness: %v\n”, unfairness)

if unfairness < float64(minUnFairness) {

minUnFairness = int64(unfairness)

}

sum += float64(arr[i] – arr[i-K+1])

avg = sum/ float64(K-1)lval = arr[i-K+1]

// fmt.Printf(“avg: %v\n”, avg)

// fmt.Printf(“lval: %v\n”, lval)

}fmt.Printf(“%v\n”, minUnFairness)

}

Submitted the code and ….its good on the timing front. But 3 test cases have wrong answers. Must be some boundary case stuff.

4) Attempt 4. It was the conversion to and fro float which caused the problem:

So just using the sum rather than average. Here goes the code which works (and passes all the test cases. Yay!)

package main

import (

“fmt”

“sort”

“math”

)

//Enter your code here. Read input from STDIN. Print output to STDOUT

var N int

fmt.Scan(&N)

var K int

fmt.Scan(&K)arr1 := make([]int, N)

for i:=0; i<N; i++ {

fmt.Scan(&arr1[i])

}

sort.Ints(arr1)arr := make([]int64, N)

for i:=0; i<N; i++ {

arr[i] = int64(arr1[i])

}

// fmt.Printf(“N: %v, K: %v\n”, N, K)

// fmt.Printf(“arr: %v\n”, arr)//prev_sz_dp := make([]int, N)

lval := arr[0]

unfairness := int64(0)// compute the avg and unfairness of the first set

sum := int64(0)

for i:=1; i<K; i++{sum += arr[i]

diff := int64( math.Abs(float64(arr[i] – arr[i-1])) )

unfairness += int64(i * (K-i)) * diff

}// fmt.Printf(“unfairness: %v\n”, unfairness)

// fmt.Printf(“avg: %v\n”, avg)

minUnFairness := unfairness// loop for the all other k sets by shifting right

// but compute the unfairness optimally (i.e by using avg and left val)

for i:=K; i<N; i++ {

unfairness -= sum – lval * int64(K-1)

unfairness += arr[i] * int64(K-1) – sum

// fmt.Printf(“unfairness: %v\n”, unfairness)

if unfairness < minUnFairness {

minUnFairness = unfairness

}

sum += arr[i] – arr[i-K+1]lval = arr[i-K+1]

// fmt.Printf(“avg: %v\n”, avg)

// fmt.Printf(“lval: %v\n”, lval)

}fmt.Printf(“%v\n”, minUnFairness)

}

Felt really good when it passed all the test cases. They had marked it as easy. But I found it quite tough.

solution for this problem in C is also available on

http://hackerrank.codingkatta.com/angry-children/