Given two lists that contain cost prices CP[] and selling prices SP[] of products respectively. The task is to maximize the profit by selling at-most ‘M’ products.
Examples:
Input: N = 5, M = 3
CP[]= {5, 10, 35, 7, 23}
SP[] = {11, 10, 0, 9, 19}
Output: 8
Profit on 0th product i.e. 11-5 = 6
Profit on 3rd product i.e. 9-7 = 2
Selling any other product will not give profit.
So, total profit = 6+2 = 8.Input: N = 4, M = 2
CP[] = {17, 9, 8, 20}
SP[] = {10, 9, 8, 27}
Output: 7
Approach:
- Store the profit/loss on buying and selling of each product i.e. SP[i]-CP[i] in an array.
- Sort that array in descending order.
- Add the positive values up to M values as positive values denote profit.
- Return Sum.
Below is the implementation of above approach:
C++
// C++ implementation of above approach:#include <bits/stdc++.h>using namespace std;// Function to find profitint solve(int N, int M, int cp[], int sp[]){ int profit[N]; // Calculating profit for each gadget for (int i = 0; i < N; i++) profit[i] = sp[i] - cp[i]; // sort the profit array in descending order sort(profit, profit + N, greater<int>()); // variable to calculate total profit int sum = 0; // check for best M profits for (int i = 0; i < M; i++) { if (profit[i] > 0) sum += profit[i]; else break; } return sum;}// Driver Codeint main(){ int N = 5, M = 3; int CP[] = { 5, 10, 35, 7, 23 }; int SP[] = { 11, 10, 0, 9, 19 }; cout << solve(N, M, CP, SP); return 0;} |
Java
// Java implementation of above approach:import java.util.*;import java.lang.*;import java.io.*;class GFG{// Function to find profitstatic int solve(int N, int M, int cp[], int sp[]){ Integer []profit = new Integer[N]; // Calculating profit for each gadget for (int i = 0; i < N; i++) profit[i] = sp[i] - cp[i]; // sort the profit array // in descending order Arrays.sort(profit, Collections.reverseOrder()); // variable to calculate total profit int sum = 0; // check for best M profits for (int i = 0; i < M; i++) { if (profit[i] > 0) sum += profit[i]; else break; } return sum;}// Driver Codepublic static void main(String args[]){ int N = 5, M = 3; int CP[] = { 5, 10, 35, 7, 23 }; int SP[] = { 11, 10, 0, 9, 19 }; System.out.println(solve(N, M, CP, SP));}}// This code is contributed// by Subhadeep Gupta |
Python3
# Python3 implementation # of above approach# Function to find profitdef solve(N, M, cp, sp) : # take empty list profit = [] # Calculating profit # for each gadget for i in range(N) : profit.append(sp[i] - cp[i]) # sort the profit array # in descending order profit.sort(reverse = True) sum = 0 # check for best M profits for i in range(M) : if profit[i] > 0 : sum += profit[i] else : break return sum# Driver Codeif __name__ == "__main__" : N, M = 5, 3 CP = [5, 10, 35, 7, 23] SP = [11, 10, 0, 9, 19] # function calling print(solve(N, M, CP, SP)) # This code is contributed# by ANKITRAI1 |
C#
// C# implementation of above approach:using System;class GFG{// Function to find profitstatic int solve(int N, int M, int[] cp, int[] sp){ int[] profit = new int[N]; // Calculating profit for each gadget for (int i = 0; i < N; i++) profit[i] = sp[i] - cp[i]; // sort the profit array // in descending order Array.Sort(profit); Array.Reverse(profit); // variable to calculate total profit int sum = 0; // check for best M profits for (int i = 0; i < M; i++) { if (profit[i] > 0) sum += profit[i]; else break; } return sum;}// Driver Codepublic static void Main(){ int N = 5, M = 3; int[] CP = { 5, 10, 35, 7, 23 }; int[] SP = { 11, 10, 0, 9, 19 }; Console.Write(solve(N, M, CP, SP));}}// This code is contributed// by ChitraNayal |
PHP
<?php // PHP implementation of above approach:// Function to find profitfunction solve($N, $M, &$cp, &$sp){ $profit = array_fill(0, $N, NULL); // Calculating profit for each gadget for ($i = 0; $i < $N; $i++) $profit[$i] = $sp[$i] - $cp[$i]; // sort the profit array // in descending order rsort($profit); // variable to calculate // total profit $sum = 0; // check for best M profits for ($i = 0; $i < $M; $i++) { if ($profit[$i] > 0) $sum += $profit[$i]; else break; } return $sum;}// Driver Code$N = 5;$M = 3;$CP = array( 5, 10, 35, 7, 23 );$SP = array( 11, 10, 0, 9, 19 );echo solve($N, $M, $CP, $SP);// This code is contributed// by ChitraNayal?> |
Javascript
<script>// Javascript implementation of above approach: // Function to find profitfunction solve(N, M, cp, sp){ let profit = new Array(N); // Calculating profit for each gadget for(let i = 0; i < N; i++) profit[i] = sp[i] - cp[i]; // Sort the profit array // in descending order profit.sort(function(a, b){return b - a;}); // Variable to calculate total profit let sum = 0; // Check for best M profits for(let i = 0; i < M; i++) { if (profit[i] > 0) sum += profit[i]; else break; } return sum;}// Driver Codelet N = 5, M = 3;let CP = [ 5, 10, 35, 7, 23 ];let SP = [ 11, 10, 0, 9, 19 ];document.write(solve(N, M, CP, SP));// This code is contributed by rag2127</script> |
Output
8
Complexity Analysis:
- Time Complexity: O(n*log(n)+m)
- Auxiliary Space: O(n)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
