# 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[1], a[2], …, a[N]}, whereÂ a[1]Â represents appetite level of first friend,Â a[2]Â 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[1], h[2], …, 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[2]+(3-1)*h[2]) + (a[4]+(3-1)*h[4]) + (a[5]+(3-1)*h[5])
= (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[1], a[2],…, a[N], which represent the initial appetite of friends. In next line there are againÂ NÂ space separated integers,Â h[1], h[2],…, 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.