Given two integers R1, R2 denoting runs scored by two players, and B1, B2 denoting balls faced by them respectively, the task is to find the minimum value of R1 * R2 that can be obtained such that R1 and R2 can be reduced by M runs satisfying the conditions R1 ? B1 and R2 ? B2.
Examples:
Input: R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3
Output: 220
Explanation: Minimum product that can be obtained is by decreasing R1 by 1 and R2 by 2, i.e. (21 – 1) x (13 – 2) = 220.Input: R1 = 7, B1 = 6, R2 = 9, B1 = 9, M = 4
Output: 54
Approach: The minimum product can be obtained by reducing the numbers completely to their limits. Reduce R1 to its limit B1 and then reduce R2 as less as possible (not exceeding M). Similarly, reduce R2 to at most B2 and then reduce R2 as less as possible (not exceeding M). The minimum product obtained in the two cases is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Utility function to find the minimum // product of R1 and R2 possible int minProductUtil(int R1, int B1, int R2, int B2, int M){ int x = min(R1-B1, M); M -= x; // Reaching to its limit R1 -= x; // If M is remaining if (M > 0) { int y = min(R2 - B2, M); M -= y; R2 -= y; } return R1 * R2;}// Function to find the minimum// product of R1 and R2int minProduct(int R1, int B1, int R2, int B2, int M){ // Case 1 - R1 reduces first int res1 = minProductUtil(R1, B1, R2, B2, M); // Case 2 - R2 reduces first int res2 = minProductUtil(R2, B2, R1, B1, M); return min(res1, res2);}// Driver Codeint main(){ // Given Input int R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3; // Function Call cout << (minProduct(R1, B1, R2, B2, M)); return 0;}// This code is contributed by maddler |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Utility function to find the minimum // product of R1 and R2 possible static int minProductUtil(int R1, int B1, int R2, int B2, int M){ int x = Math.min(R1-B1, M); M -= x; // Reaching to its limit R1 -= x; // If M is remaining if (M > 0) { int y = Math.min(R2 - B2, M); M -= y; R2 -= y; } return R1 * R2;}// Function to find the minimum// product of R1 and R2static int minProduct(int R1, int B1, int R2, int B2, int M){ // Case 1 - R1 reduces first int res1 = minProductUtil(R1, B1, R2, B2, M); // Case 2 - R2 reduces first int res2 = minProductUtil(R2, B2, R1, B1, M); return Math.min(res1, res2);}// Driver Codepublic static void main (String[] args) { // Given Input int R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3; // Function Call System.out.print((minProduct(R1, B1, R2, B2, M)));}}// This code is contributed by shivanisinghss2110 |
Python3
# Python program for the above approach# Utility function to find the minimum# product of R1 and R2 possibledef minProductUtil(R1, B1, R2, B2, M): x = min(R1-B1, M) M -= x # Reaching to its limit R1 -= x # If M is remaining if M > 0: y = min(R2-B2, M) M -= y R2 -= y return R1 * R2 # Function to find the minimum# product of R1 and R2def minProduct(R1, B1, R2, B2, M): # Case 1 - R1 reduces first res1 = minProductUtil(R1, B1, R2, B2, M) # case 2 - R2 reduces first res2 = minProductUtil(R2, B2, R1, B1, M) return min(res1, res2)# Driver Codeif __name__ == '__main__': # Given Input R1 = 21; B1 = 10; R2 = 13; B2 = 11; M = 3 # Function Call print(minProduct(R1, B1, R2, B2, M)) |
C#
// C# program for the above approachusing System;class GFG{ // Utility function to find the minimum // product of R1 and R2 possible static int minProductUtil(int R1, int B1, int R2, int B2, int M){ int x = Math.Min(R1-B1, M); M -= x; // Reaching to its limit R1 -= x; // If M is remaining if (M > 0) { int y = Math.Min(R2 - B2, M); M -= y; R2 -= y; } return R1 * R2;}// Function to find the minimum// product of R1 and R2static int minProduct(int R1, int B1, int R2, int B2, int M){ // Case 1 - R1 reduces first int res1 = minProductUtil(R1, B1, R2, B2, M); // Case 2 - R2 reduces first int res2 = minProductUtil(R2, B2, R1, B1, M); return Math.Min(res1, res2);}// Driver Codepublic static void Main (String[] args) { // Given Input int R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3; // Function Call Console.Write((minProduct(R1, B1, R2, B2, M)));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Utility function to find the minimum // product of R1 and R2 possible function minProductUtil(R1, B1, R2, B2, M){ let x = Math.min(R1 - B1, M); M -= x; // Reaching to its limit R1 -= x; // If M is remaining if (M > 0) { let y = Math.min(R2 - B2, M); M -= y; R2 -= y; } return R1 * R2;}// Function to find the minimum// product of R1 and R2function minProduct(R1, B1, R2, B2, M){ // Case 1 - R1 reduces first let res1 = minProductUtil(R1, B1, R2, B2, M); // Case 2 - R2 reduces first let res2 = minProductUtil(R2, B2, R1, B1, M); return Math.min(res1, res2);}// Driver Code// Given Inputlet R1 = 21, B1 = 10, R2 = 13, B2 = 11, M = 3;// Function Calldocument.write((minProduct(R1, B1, R2, B2, M)));// This code is contributed by code_hunt</script> |
220
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
