IBM Online Assessment for Software Developer role

Madam C.J. Walker is historically renowned for becoming the first African-American businesswoman in America. One of her business plans involving the sale of cosmetics and perfumes for women is a...

Madam C.J. Walker is historically renowned for becoming the first African-American businesswoman in America. One of her business plans involving the sale of cosmetics and perfumes for women is a modification of the standard 0-1 knapsack problem.

Walker\'s business plan begins with an array of n items. She wants to buy products and resell them for profit. The cost of buying the item is cost, and it earns her a profit of 21. She has a total of x amount of money.

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.

**Example
**
Suppose there n = 5 items with costs cost = [10, 20, 14, 40, 50], and the initial amount of money that Walker has is x = 70

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.

returns-
max Profit: an integer denoting the maximum profit that can be obtained % (10^9+7)

Constraints

1<=n<=10^5

1<= cost[i]<=10^5

0<=x<= 10^9

TC 0 :
3
3
4
1
8

cost size is 3 cost [3, 4, 1] x=8

Output : 7

TC1 :

5
19
78
27
15
20
25

cost size is 5 cost [19, 78, 27, 18,20] x=25

output :16

function
int maxProfit(vector& cost, int x) {
// code
}

How to solve i used modified 0 1 knapsack only few test case

passed