Mangoes – HackerRank Solution

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

Task

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 i^th 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 = {b₁, b₂…b_k}, are invited to party, then total number of mangoes consumed will be (a[b₁]+(k-1)*h[b₁]) + (a[b₂]+(k-1)*h[b₂]) + … + (a[b_k]+(k-1)*h[b_k]).

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 * 10⁴
• 1 ≤ M ≤ 2.5 * 10¹⁵
• 1 ≤ a[i], h[i] ≤ 10⁶ , 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.