Description
Solutions
Max Profit
👩‍🎓 NEW GRAD

Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit % (10 ^ 9 + 7) where % denotes modulo operator.

Function Description

Complete the function maxProfit in the editor.

maxProfit has the following parameters:

  • int[] cost: an array of integers representing the cost of each item
  • int x: the initial amount of money Walker has

    • Returns

    int: the maximum profit that can be obtained modulo (10^9+7)

    Example 1: 

    Input:  cost = [3, 4, 1], x = 8
    Output: 7 
    Explanation:
    
:)

    Example 2: 

    Input:  cost = [19, 78, 27, 15, 20, 25], x = 25
    Output: 16 
    Explanation:
    
:)

    Example 3: 

    Input:  cost = [10, 20, 14, 40, 50], x = 70
    Output: 20 
    Explanation:
    

Some possible combination of items Walker can buy are:


She can buy items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 = 7


She can buy items 0 and 4 for a cost of 60 and obtain a profit of 2 ^ 0 + 2 ^ 4 = 17


She can buy items 1 and 4 for a cost of 70 and obtain a profit of 2 ^ 1 + 2 ^ 4 = 18


She can buy items 2 and 4 for a cost of 64 and obtain a profit of 2 ^ 2 + 2 ^ 4 = 20


Out of all the possible combinations, the maximum profit obtained is by buying items 2 and 4 for a cost of 64 to obtain a profit of 20.
    Constraints:
      • 1 <= n <= 10^5
      • 1 <= cost[i] <= 10^5
      • 0 <= x <= 10^9
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: