Maximum number of mangoes that can be bought

Maximum number of mangoes that can be bought

Given two integers W and C, representing the number of watermelons and coins, the task is to find the maximum number of mangoes that can be bought given that each mango costs 1 watermelon and X coins and y coins can be earned selling a watermelon.

Examples:

Input: W = 10, C = 10, X = 1, Y = 1
Output: 10
Explanation: The most optimal way is to use 10 watermelons and 10 coins to buy 10 mangoes. Hence, the maximum number of mangoes that can be bought is 10.

Input: W = 4, C = 8, X = 4, Y = 4
Output: 3
Explanation: The most optimal way is to sell one watermelon. Then, the number of coins increases by 4. Therefore, the total number of coins becomes 12. Therefore, 3 watermelons and 12 coins can be used to buy 3 mangoes. Hence, the maximum number of mangoes that can be bought is 3.

Approach: This problem can be solved using binary search. The idea is to find the maximum number of mangoes in the search space. Follow the steps below to solve the problem:

• Initialize a variable ans as 0 to store the required result.
• Initialize two variables l as 0, r as W to store the boundary regions of the search space for binary search.
• Loop while l≤r and perform the following steps:
  • Store the middle value in a variable mid as (l+r)/2.
  • Check if mid number of mangoes can be bought using the given value of W, C, x, and y.
  • If true, then update ans to mid and search in the right part of mid by updating l to mid+1. Otherwise, update the value of r to mid-1.
• Print the value of ans as the result.

Below is the implementation of the above approach:

C++14

#include <bits/stdc++.h> using namespace std; bool check(int n, int m, int x, int y, int vl) {          int temp = m;               if (vl > n)         return false;               int ex = n - vl;               ex *= y;          temp += ex;               int cr = temp / x;               if (cr >= vl)         return true;          return false; } int maximizeMangoes(int n, int m, int x, int y) {          int l = 0, r = n;          int ans = 0;          while (l <= r) {                  int mid = l + (r - l) / 2;                           if (check(n, m, x, y, mid)) {             ans = mid;             l = mid + 1;         }                  else             r = mid - 1;     }          return ans; } int main() {          int W = 4, C = 8, x = 4, y = 4;          cout << maximizeMangoes(W, C, x, y);     return 0; }

C#

using System; class GFG{ static bool check(int n, int m, int x,                   int y, int vl) {                int temp = m;               if (vl > n)         return false;               int ex = n - vl;               ex *= y;          temp += ex;               int cr = temp / x;               if (cr >= vl)         return true;          return false; } static int maximizeMangoes(int n, int m, int x, int y) {                int l = 0, r = n;          int ans = 0;          while (l <= r)     {                            int mid = l + (r - l) / 2;                           if (check(n, m, x, y, mid))         {             ans = mid;             l = mid + 1;         }                  else             r = mid - 1;     }          return ans; } public static void Main() {                int W = 4, C = 8, x = 4, y = 4;          Console.Write(maximizeMangoes(W, C, x, y)); } }

Output: 

3

Time Complexity: O(log(W))
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets