# Mangoes – HackerRank Solution

In this post, we will solve Mangoes HackerRank Solution. This problem (Mangoes) is a part of HackerRank Functional Programming series.

Contents

It’s the time of the year when fresh mangoes are available. Bob has a very good day at his school today and decides to treat some of his friends with mangoes. There are N people in his friend circle, and he has M mangoes. Initial appetite level of the friends is represented by an array a = {a, a, …, a[N]}, where a represents appetite level of first friend, a represents appetite level of second friend, and so on. Apart from this, each friend has a happiness factor which is represented by an array h = {h, h, …, h[N]}. If ith friend is invited to the party, and he finds that there are p other friends, then he will eat a[i] + p*h[i] mangoes.

Thus, if k friends, indexed b = {b1, b2…bk}, are invited to party, then total number of mangoes consumed will be (a[b1]+(k-1)*h[b1]) + (a[b2]+(k-1)*h[b2]) + … + (a[bk]+(k-1)*h[bk]).

For example, if there are N = 5 friends whose initial appetite is represented by a = {2, 5, 3, 2, 4} and happiness factor is represented by h = {30, 40, 10, 20, 30}. Suppose Bob invites k = 3 friends, indexed {2, 4, 5}, then total number of mangoes eaten will be

``````= (a+(3-1)*h) + (a+(3-1)*h) + (a+(3-1)*h)
= (5+2*40) + (2+2*20) + (4+2*30)
= 85 + 42 + 64
= 191``````

Bob is wondering what is the maximum number of friends he can invite to his treat, so that, their hunger can be completely satisfied.

Note: It is not necessary that all mangoes have to be consumed.

## Input

The first line contains two space separated integers, N M, where N is the number of friends, and M is the number of mangoes Bob has. Then in next line follows N space separated integers, a, a,…, a[N], which represent the initial appetite of friends. In next line there are again N space separated integers, h, h,…, h[N], representing the happiness factor for friends.

## Output

Print the maximum number of friends which Bob can invite to his treat.

## Constraints

• 1 ≤ N ≤ 5 * 104
• 1 ≤ M ≤ 2.5 * 1015
• 1 ≤ a[i], h[i] ≤ 106 , where i ∈ [1, N]

Sample Input #00

``````5 200
2 5 3 2 4
30 40 10 20 30``````

Sample Output #00

``3``

Sample Input #01

``````2 100
3 4
1 2``````

Sample Output #01

``2``

Explanation

Test Case #00: This case is explaned in the statement.
Test Case #01: We can call both people. They will consume (3 + 1 * 1) + (4 + 1 * 2) = 4 + 6 = 10 mangoes. Hence, only 10 mangoes are consumed.

## Solution – Mangoes – HackerRank Solution

Scala

```import java.util.Scanner

object Solution {

def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

val n = sc.nextInt
val m = sc.nextLong
val a = (0 until n).map(_ => sc.nextInt)
val h = (0 until n).map(_ => sc.nextInt)

val friends = a.indices.map(i => Friend(a(i), h(i)))

sc.close()

println(solve(friends, m))
}

def solve(friends: IndexedSeq[Friend], m: Long): Int = {
@scala.annotation.tailrec
def inner(min: Int, max: Int): Int = if (min <= max) {
val middle = (min + max) / 2

val sortedFriends = friends.sortBy(_.appetite(middle))
val totalAppetite = sortedFriends.take(middle)
.map(_.appetite(middle))
.sum

val (nextMin, nextMax) = if (totalAppetite <= m) (middle + 1, max) else (min, middle - 1)
inner(nextMin, nextMax)
} else max

inner(0, friends.length)
}

case class Friend(a: Long, h: Long) {
def appetite(cnt: Int): Long = a + (cnt - 1) * h
}

}
```

Note: This problem (Mangoes) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.