Minimum price required to obtain N items of given types
Given integers X, Y, and Z, representing prices of 3 items A, B and C respectively, and two integers a and b, denoting count of two types of items. The task is to calculate the minimum price required to obtain N items of the type A, B or C, where A requires 2 item of type a, B requires 3 items of type b, and C requires 1 item of type a and 1 item of type b.
Examples:
Input: X = 300, Y = 200, Z = 100, N = 4, a = 3, b = 7
Output: 500
Explanation: Four items can be formed by buying 3 C’s (3*100 = 300) using 3 a’s and 3 b’s, and 1 B(1*200 = 200) using 3 b’s. Final price = 300 + 200 = 500, which is minimum possible.Input: X=300, Y=150, Z=200, N=5, a=6, b=4
Output: 1100
Approach: The above problem can be solved by fixing the number of one item and checking the price required to form the remaining items. Follow the steps below to solve the problem:
- Initialize variable, say minimum_bill to store the minimum price required to buy N items.
- Iterate over the range C, less than or equal to N.
- Initialize variables, say maxorders_A equals (a – orders_C) / 2 and maxorders_B equals (b – orders_C) / 3.
- Check if maxorders_A + maxorders_B + maxorders_C is less than N, then continue.
- If X is less than Y, then find orders_A as min(maxorders_A, N – orders_C) and orders_B as N – orders_C – orders_A.
- Otherwise, find orders_B as min(maxorders_B, N – orders_C) and orders_A as N – orders_C – orders_B.
- Calculate the required bill in a variable, say bill, as (X * orders_A) + (Y * orders_B) + (Z * orders_C).
- In each iteration, update the minimum_bill as minimum of minimum_bill and bill.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the minimum price void FindBill( int X, int Y, int Z, int N, int a, int b) { // Stores the amount required int minimum_bill = 10000000; // Iterating over total number // of possible items of type C for ( int orders_C = 0; orders_C <= N; orders_C++) { // If count of a and b are less // than minimum required of type C if (a < orders_C or b < orders_C) break ; // Maximum number of orders of type A int maxorders_A = (a - orders_C) / 2; // Maximum number of orders of type +B int maxorders_B = (b - orders_C) / 3; // Initializing the required // number of orders for A and B int orders_A = 0; int orders_B = 0; // Total items should be // greater than or equal to N if ((maxorders_A + maxorders_B + orders_C) < N) { continue ; } // If cost of A < cost of B if (X < Y) { // Total orders of A will be minimum // of maximum orders of A or just // remaining orders required orders_A = min(maxorders_A, N - orders_C); // Remaining number of orders for B orders_B = N - orders_C - orders_A; } // If cost of A > cost of B else { // Total orders of B will be minimum // of maximum orders of B or just // remaining orders required orders_B = min(maxorders_B, N - orders_C); // Remaining number of orders for A orders_A = N - orders_C - orders_B; } // Calculating bill int bill = (X * orders_A) + (Y * orders_B) + (Z * orders_C); // Updating minimum_bill minimum_bill = min(bill, minimum_bill); } // If ordering N items is not possible if (minimum_bill == 10000000) minimum_bill = 0; // Printing minimum bill cout << minimum_bill << endl; } // Driver Code int main() { // Given Input int X = 300, Y = 150, Z = 200, N = 5, a = 6, b = 4; /// Function Call FindBill(X, Y, Z, N, a, b); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to calculate the minimum price static void FindBill( int X, int Y, int Z, int N, int a, int b) { // Stores the amount required int minimum_bill = 10000000 ; // Iterating over total number // of possible items of type C for ( int orders_C = 0 ; orders_C <= N; orders_C++) { // If count of a and b are less // than minimum required of type C if (a < orders_C || b < orders_C) break ; // Maximum number of orders of type A int maxorders_A = (a - orders_C) / 2 ; // Maximum number of orders of type +B int maxorders_B = (b - orders_C) / 3 ; // Initializing the required // number of orders for A and B int orders_A = 0 ; int orders_B = 0 ; // Total items should be // greater than or equal to N if ((maxorders_A + maxorders_B + orders_C) < N) { continue ; } // If cost of A < cost of B if (X < Y) { // Total orders of A will be minimum // of maximum orders of A or just // remaining orders required orders_A = Math.min(maxorders_A, N - orders_C); // Remaining number of orders for B orders_B = N - orders_C - orders_A; } // If cost of A > cost of B else { // Total orders of B will be minimum // of maximum orders of B or just // remaining orders required orders_B = Math.min(maxorders_B, N - orders_C); // Remaining number of orders for A orders_A = N - orders_C - orders_B; } // Calculating bill int bill = (X * orders_A) + (Y * orders_B) + (Z * orders_C); // Updating minimum_bill minimum_bill = Math.min(bill, minimum_bill); } // If ordering N items is not possible if (minimum_bill == 10000000 ) minimum_bill = 0 ; // Printing minimum bill System.out.println(minimum_bill); } // Driver Code public static void main (String[] args) { // Given Input int X = 300 , Y = 150 , Z = 200 , N = 5 , a = 6 , b = 4 ; /// Function Call FindBill(X, Y, Z, N, a, b); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach # Function to calculate the minimum price def FindBill(X, Y, Z, N, a, b): # Stores the amount required minimum_bill = 10000000 ; # Iterating over total number # of possible items of type C for orders_C in range ( 0 , N + 1 ): # If count of a and b are less # than minimum required of type C if (a < orders_C or b < orders_C): break ; # Maximum number of orders of type A maxorders_A = (a - orders_C) / / 2 ; # Maximum number of orders of type +B maxorders_B = (b - orders_C) / / 3 ; # Initializing the required # number of orders for A and B orders_A = 0 ; orders_B = 0 ; # Total items should be # greater than or equal to N if (maxorders_A + maxorders_B + orders_C < N): continue ; # If cost of A < cost of B if (X < Y): # Total orders of A will be minimum # of maximum orders of A or just # remaining orders required orders_A = min (maxorders_A, N - orders_C); # Remaining number of orders for B orders_B = N - orders_C - orders_A; # If cost of A > cost of B else : # Total orders of B will be minimum # of maximum orders of B or just # remaining orders required orders_B = min (maxorders_B, N - orders_C); # Remaining number of orders for A orders_A = N - orders_C - orders_B; # Calculating bill bill = X * orders_A + Y * orders_B + Z * orders_C; # Updating minimum_bill minimum_bill = min (bill, minimum_bill); # If ordering N items is not possible if (minimum_bill = = 10000000 ): minimum_bill = 0 ; # Printing minimum bill print (minimum_bill); # Driver Code # Given Input X = 300 Y = 150 Z = 200 N = 5 a = 6 b = 4 #/ Function Call FindBill(X, Y, Z, N, a, b); # This code is contributed by gfgking. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to calculate the minimum price static void FindBill( int X, int Y, int Z, int N, int a, int b) { // Stores the amount required int minimum_bill = 10000000; // Iterating over total number // of possible items of type C for ( int orders_C = 0; orders_C <= N; orders_C++) { // If count of a and b are less // than minimum required of type C if (a < orders_C || b < orders_C) break ; // Maximum number of orders of type A int maxorders_A = (a - orders_C) / 2; // Maximum number of orders of type +B int maxorders_B = (b - orders_C) / 3; // Initializing the required // number of orders for A and B int orders_A = 0; int orders_B = 0; // Total items should be // greater than or equal to N if ((maxorders_A + maxorders_B + orders_C) < N) { continue ; } // If cost of A < cost of B if (X < Y) { // Total orders of A will be minimum // of maximum orders of A or just // remaining orders required orders_A = Math.Min(maxorders_A, N - orders_C); // Remaining number of orders for B orders_B = N - orders_C - orders_A; } // If cost of A > cost of B else { // Total orders of B will be minimum // of maximum orders of B or just // remaining orders required orders_B = Math.Min(maxorders_B, N - orders_C); // Remaining number of orders for A orders_A = N - orders_C - orders_B; } // Calculating bill int bill = (X * orders_A) + (Y * orders_B) + (Z * orders_C); // Updating minimum_bill minimum_bill = Math.Min(bill, minimum_bill); } // If ordering N items is not possible if (minimum_bill == 10000000) minimum_bill = 0; // Printing minimum bill Console.Write(minimum_bill); } // Driver Code public static void Main() { // Given Input int X = 300, Y = 150, Z = 200, N = 5, a = 6, b = 4; /// Function Call FindBill(X, Y, Z, N, a, b); } } // This code is contributed by ipg2016107. |
Javascript
<script> // Javascript program for the above approach // Function to calculate the minimum price function FindBill(X, Y, Z, N, a, b) { // Stores the amount required let minimum_bill = 10000000; // Iterating over total number // of possible items of type C for (let orders_C = 0; orders_C <= N; orders_C++) { // If count of a and b are less // than minimum required of type C if (a < orders_C || b < orders_C) break ; // Maximum number of orders of type A let maxorders_A = Math.floor((a - orders_C) / 2); // Maximum number of orders of type +B let maxorders_B = (b - orders_C) / 3; // Initializing the required // number of orders for A and B let orders_A = 0; let orders_B = 0; // Total items should be // greater than or equal to N if (maxorders_A + maxorders_B + orders_C < N) { continue ; } // If cost of A < cost of B if (X < Y) { // Total orders of A will be minimum // of maximum orders of A or just // remaining orders required orders_A = Math.min(maxorders_A, N - orders_C); // Remaining number of orders for B orders_B = N - orders_C - orders_A; } // If cost of A > cost of B else { // Total orders of B will be minimum // of maximum orders of B or just // remaining orders required orders_B = Math.min(maxorders_B, N - orders_C); // Remaining number of orders for A orders_A = N - orders_C - orders_B; } // Calculating bill let bill = X * orders_A + Y * orders_B + Z * orders_C; // Updating minimum_bill minimum_bill = Math.min(bill, minimum_bill); } // If ordering N items is not possible if (minimum_bill == 10000000) minimum_bill = 0; // Printing minimum bill document.write(minimum_bill); } // Driver Code // Given Input let X = 300, Y = 150, Z = 200, N = 5, a = 6, b = 4; /// Function Call FindBill(X, Y, Z, N, a, b); // This code is contributed by gfgking. </script> |
1100
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us