#Hackerrank
#Problem Solving
## Example:

### Some possible combinations of items the mechanic can buy are:

## Write a code in Python:

### parameter(s):

## Constraints:

## Solution in Python:

The below-given problem is a modification of the standard 0-1 knapsack problem.

An automobile mechanic wants to buy a set of spare parts from a manufacturing unit. The cost of buying the ith spare part is cost[i], and the mechanic charges an amount of 2i for replacing the ith spare part with a new one. The manufacturing unit deals in a total of n items. The mechanic has a total of x amount of money, which the mechanic can spend on buying spare parts.

The goal is to maximise the total amount of money the mechanic can earn for a given amount x. As the answer can be rather large, report the answer as moneyEarned % (109+7), where % denotes modulo operator.

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

The mechanic can buy items 0, 1, and 2 for a cost of 44 and earn an amount of 20 + 21 + 22= 7.

The mechanic can buy items 0 and 4 for a cost of 60 and earn an amount of 20 + 24= 17.

The mechanic can buy items 1 and 4 for a cost of 70 and earn an amount of 21+ 24= 18.

The mechanic can buy items 2 and 4 for a cost of 64 and earn an amount of 22 + 24 = 20.

Out of all the possible combinations, the maximum money earned is by buying items 2 and 4 for a cost of 64 to obtain a value of 20.

Complete function findMaximumMoneyEarned (cost, x):

cost: an array of integers with cost[i] denoting the cost of buying the ith item.

x: an integer denoting the amount of money the mechanic has.

Function returns :

int: an integer denoting the maximum amount of money the mechanic can earn % (109+7).

1≤ n≤ 105

1≤ cost[i]≤ 105

0≤ x≤ 109

MOD = 10**9 + 7

def findMaximumMoneyEarned(cost, x):

n = len(cost)

# Initialize a 1D list to store the maximum money earned

dp = [0] * (x + 1)

for i in range(1, n + 1):

for j in range(x, cost[i - 1] - 1, -1):

# Calculate max money either buy or not buy the spare part (dp[j])

# print(f"Considering spare part {i}, budget {j}:")

# If the cost of the spare part > budget, skip it

if cost[i - 1] > j:

dp[j] = dp[j]

# print(f" Skip part {i} (cost={cost[i-1]})")

else:

dp[j] = max(dp[j], dp[j - cost[i - 1]] + 2 ** (i - 1))

#print(f" Buy part {i} (cost={cost[i-1]})")

# The answer is stored in dp[x]

return dp[x] % MOD

# Example usage

cost = [10, 20, 14, 40, 50]

x = 70

result = findMaximumMoneyEarned(cost, x)

print(result) # Output should be 20

cost = [3, 4, 1]

x = 8

result = findMaximumMoneyEarned(cost, x)

print(result) # Output should be 7

cost = [19, 78, 27, 18, 20]

x = 25

result = findMaximumMoneyEarned(cost, x)

print(result) # Output should be 16

Sample Input 1:

cost = [3, 4, 1]

x = 8

Sample Output:

7

Explanation:

The mechanic can buy all the items since their total cost is less than or equal to the remaining money.

The total money the mechanic would earn would be 20 + 21 + 22 = 7. The output would be 7 % 109+7 , i.e. 7.

Sample Case 1:

cost= [19, 78, 27, 18, 20]

x = 25

Sample Output:

16

Explanation:

The optimal solution would be to buy the last item, generating an amount of 24 = 16. The output will be 16 % (109+7), i.e. 16.

Explore more

#JavaScript #Python #Hackerrank #Motivation #AI #Interview #React.js #Testing #SQL #Selenium #LeetCode #Problem Solving #Machine learning #IT #API #Java #GPT #AWS #Algorithms #Github #Projects #Jobs #Django #Microservice #Certifications #Node.js #TCS #Google #Story #Pip #Data Science #Postman #Health #Twitter #Elon Musk

#JavaScript #Python #Hackerrank #Motivation #AI #Interview #React.js #Testing #SQL #Selenium #LeetCode #Problem Solving #Machine learning #IT #API #Java #GPT #AWS #Algorithms #Github #Projects #Jobs #Django #Microservice #Certifications #Node.js #TCS #Google #Story #Pip #Data Science #Postman #Health #Twitter #Elon Musk

Related Blogs

View More

1. Basic SQL Select Query of Hacker Rank.

Author: neptune | 20th-Apr-2022

#SQL #Hackerrank

Problem Statement : Query all columns for all American cities in the CITY table with populations larger than 100000. The CountryCode for America is USA...

Author: neptune | 20th-Apr-2022

#SQL #Hackerrank

Problem Statement : Query all columns for all American cities in the CITY table with populations larger than 100000. The CountryCode for America is USA...

AngularJS - Know Tech Frameworks | Fresco Play

Author: neptune | 05th-Nov-2023

#Hackerrank #Problem Solving

Build an application that displays the framework details using AngularJS routing. We will build an application that displays the Tech Frontend and Backend frameworks...

Author: neptune | 05th-Nov-2023

#Hackerrank #Problem Solving

Build an application that displays the framework details using AngularJS routing. We will build an application that displays the Tech Frontend and Backend frameworks...

PySpark Milestone Black Friday Sales Data | Fresco Play Hackerrank

Author: neptune | 05th-Nov-2023

#Data Science #Hackerrank

Welcome to the Spark Challenge. You are provided with the Black Friday sales data and we as a big data developer needs to analyze and fetch the required data...

Author: neptune | 05th-Nov-2023

#Data Science #Hackerrank

Welcome to the Spark Challenge. You are provided with the Black Friday sales data and we as a big data developer needs to analyze and fetch the required data...

Python - Number Based Problem | Hackerrank

Author: neptune | 17th-Aug-2023

#Hackerrank #Problem Solving

Determine whether the number in descending order is a prime or not. If the number is a prime, then print "Sorted Number is a prime number," otherwise, print "Sorted Number is not a prime number."..

Author: neptune | 17th-Aug-2023

#Hackerrank #Problem Solving

Determine whether the number in descending order is a prime or not. If the number is a prime, then print "Sorted Number is a prime number," otherwise, print "Sorted Number is not a prime number."..

View More

anonymous | Sept. 19, 2023, 12:52 a.m.

Awesome!