Maximize profit that can be earned by selling an item among N buyers
Given an array arr[] of size N, the task is to find the price of the item such that the profit earned by selling the item among N buyers is maximum possible consisting of budgets of N buyers. An item can be sold to any buyer if the budget of the buyer is greater than or equal to the price of the item.
Examples:
Input: arr[] = {34, 78, 90, 15, 67}
Output: 67
Explanation: For the item with price 67, the number of buyers who can buy the item is 3. Therefore, the profit earned is 67 * 3 = 201, which is maximum.Input: arr[] = {300, 50, 32, 43, 42}
Output: 300
Naive Approach: Follow the steps below to solve the problem:
- Initialize two variables, say price and profit as 0, to store the profit by selling an item and the possible price of the item respectively.
- Traverse the given array arr[] and perform the following steps:
- Set the price of the item as arr[i].
- Find the number of buyers whose budget is at least arr[i] by traversing the given array. Let the value be count.
- If the value of count*arr[i] is greater than the profit then update the profit as count*arr[i] and the price as arr[i].
- After completing the above steps, print the value of the price as the resultant price.
Below is the implementation of the above approach:
C++
#include <iostream> #include <climits> #include <algorithm> using namespace std; // Function to find the maximum profit // earned by selling an item among // N buyers int maximumProfit( int arr[], int n) { // Stores the maximum profit int ans = INT_MIN; // Stores the price of the item int price = 0; // Traverse the array for ( int i = 0; i < n; i++) { // Count of buyers with // budget >= arr[i] int count = 0; for ( int j = 0; j < n; j++) { if (arr[i] <= arr[j]) { // Increment count count++; } } // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver code int main() { int arr[] = { 22, 87, 9, 50, 56, 43 }; cout<<maximumProfit(arr,6); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the maximum profit // earned by selling an item among // N buyers public static int maximumProfit( int arr[]) { // Stores the maximum profit int ans = Integer.MIN_VALUE; // Stores the price of the item int price = 0 ; int n = arr.length; // Traverse the array for ( int i = 0 ; i < n; i++) { // Count of buyers with // budget >= arr[i] int count = 0 ; for ( int j = 0 ; j < n; j++) { if (arr[i] <= arr[j]) { // Increment count count++; } } // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver Code public static void main(String[] args) { int arr[] = { 22 , 87 , 9 , 50 , 56 , 43 }; System.out.print( maximumProfit(arr)); } } |
Python3
import sys # Function to find the maximum profit # earned by selling an item among # N buyers def maximumProfit(arr, n): # Stores the maximum profit ans = - sys.maxsize - 1 # Stores the price of the item price = 0 # Traverse the array for i in range (n): # Count of buyers with # budget >= arr[i] count = 0 for j in range (n): if (arr[i] < = arr[j]): # Increment count count + = 1 # Update the maximum profit if (ans < count * arr[i]): price = arr[i] ans = count * arr[i] # Return the maximum possible # price return price; # Driver code if __name__ = = '__main__' : arr = [ 22 , 87 , 9 , 50 , 56 , 43 ] print (maximumProfit(arr, 6 )) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum profit // earned by selling an item among // N buyers public static int maximumProfit( int [] arr) { // Stores the maximum profit int ans = Int32.MinValue; // Stores the price of the item int price = 0; int n = arr.Length; // Traverse the array for ( int i = 0; i < n; i++) { // Count of buyers with // budget >= arr[i] int count = 0; for ( int j = 0; j < n; j++) { if (arr[i] <= arr[j]) { // Increment count count++; } } // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver Code public static void Main( string [] args) { int [] arr = { 22, 87, 9, 50, 56, 43 }; Console.Write( maximumProfit(arr)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // Function to find the maximum profit // earned by selling an item among // N buyers function maximumProfit(arr, n) { // Stores the maximum profit var ans = -100000;; // Stores the price of the item var price = 0; // Traverse the array for ( var i = 0; i < n; i++) { // Count of buyers with // budget >= arr[i] var count = 0; for ( var j = 0; j < n; j++) { if (arr[i] <= arr[j]) { // Increment count count++; } } // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } arr = [ 22, 87, 9, 50, 56, 43 ]; document.write(maximumProfit(arr,6)); </script> |
43
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by sorting the array such that the count of elements greater than the current element can be calculated in O(1) time. Follow the steps below to solve the problem:
- Initialize two variables, say price and profit as 0, to store the profit by selling an item and the possible price of the item respectively.
- Sort the array in ascending order.
- Traverse the given array arr[i] and perform the following steps:
- Set the price of the item as arr[i].
- Now, the number of buyers whose budget is at least arr[i] is given by (N – i). Let the value be count.
- If the value of count*arr[i] is greater than the profit then update the profit as count*arr[i] and the price as arr[i].
- After completing the above steps, print the value of the price as the resultant price.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <climits> #include <algorithm> using namespace std; // Function to find the maximum profit // earned by selling an item among // N buyers int maximumProfit( int arr[], int N) { // Stores the maximum profit int ans = INT_MIN; // Stores the price of the item int price = 0; // Sort the array sort(arr, arr + N); // Traverse the array for ( int i = 0; i < N; i++) { // Count of buyers with // budget >= arr[i] int count = (N - i); // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver code int main() { int arr[] = { 22, 87, 9, 50, 56, 43 }; cout << maximumProfit(arr,6); return 0; } // This code is contributed by le0. |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the maximum profit // earned by selling an item among // N buyers public static int maximumProfit( int arr[]) { // Stores the maximum profit int ans = Integer.MIN_VALUE; // Stores the price of the item int price = 0 ; // Sort the array Arrays.sort(arr); int N = arr.length; // Traverse the array for ( int i = 0 ; i < N; i++) { // Count of buyers with // budget >= arr[i] int count = (N - i); // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver Code public static void main(String[] args) { int arr[] = { 22 , 87 , 9 , 50 , 56 , 43 }; System.out.print( maximumProfit(arr)); } } |
C#
// C# Program to implement // the above approach using System; class GFG { // Function to find the maximum profit // earned by selling an item among // N buyers public static int maximumProfit( int [] arr) { // Stores the maximum profit int ans = Int32.MinValue; // Stores the price of the item int price = 0; // Sort the array Array.Sort(arr); int N = arr.Length; // Traverse the array for ( int i = 0; i < N; i++) { // Count of buyers with // budget >= arr[i] int count = (N - i); // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver Code public static void Main(String[] args) { int [] arr = { 22, 87, 9, 50, 56, 43 }; Console.WriteLine( maximumProfit(arr)); } } // This code is contributed by splevel62. |
Python3
# Python3 program for the above approach import sys # Function to find the maximum profit # earned by selling an item among # N buyers def maximumProfit(arr, N): # Stores the maximum profit ans = - sys.maxsize - 1 # Stores the price of the item price = 0 # Sort the array arr.sort() # Traverse the array for i in range (N): # Count of buyers with # budget >= arr[i] count = (N - i) # Update the maximum profit if (ans < count * arr[i]): price = arr[i] ans = count * arr[i] # Return the maximum possible # price return price # Driver code if __name__ = = "__main__" : arr = [ 22 , 87 , 9 , 50 , 56 , 43 ] print (maximumProfit(arr, 6 )) # This code is contributed by ukasp |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum profit // earned by selling an item among // N buyers function maximumProfit( arr, N) { // Stores the maximum profit let ans = Number.MIN_VALUE; // Stores the price of the item let price = 0; // Sort the array arr.sort( function (a,b){ return a-b}); // Traverse the array for (let i = 0; i < N; i++) { // Count of buyers with // budget >= arr[i] let count = (N - i); // Update the maximum profit if (ans < count * arr[i]) { price = arr[i]; ans = count * arr[i]; } } // Return the maximum possible // price return price; } // Driver code let arr = [ 22, 87, 9, 50, 56, 43 ]; document.write( maximumProfit(arr,6)); </script> |
43
Time Complexity: O(N * log N)
Auxiliary Space: O(1)