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

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

Related Blogs

View More

5. Solution of Hacker Rank Weather Observation Station 8.

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Query the list of CITY names from STATION which have vowels (i.e., a, e, i, o, and u) as both their first and last characters. Your result cannot contain duplicates...

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Query the list of CITY names from STATION which have vowels (i.e., a, e, i, o, and u) as both their first and last characters. Your result cannot contain duplicates...

The Blunder | Hackerrank

Author: neptune | 21st-Nov-2022

#SQL #Hackerrank

Write a query calculating the amount of error (i.e.: average monthly salaries), and round it up to the next integer...

Author: neptune | 21st-Nov-2022

#SQL #Hackerrank

Write a query calculating the amount of error (i.e.: average monthly salaries), and round it up to the next integer...

7.Solution of Hacker Rank The Report

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : generate a report containing three columns: Name, Grade and Mark. Ketty doesn't want the NAMES of those students who received a grade lower than 8...

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : generate a report containing three columns: Name, Grade and Mark. Ketty doesn't want the NAMES of those students who received a grade lower than 8...

4. Solution of Hacker Rank Weather Observation Station 6.

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Query the list of CITY names starting with vowels (i.e., a, e, i, o, or u) from STATION. Your result cannot contain duplicates...

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Query the list of CITY names starting with vowels (i.e., a, e, i, o, or u) from STATION. Your result cannot contain duplicates...

3. Solution of Hacker Rank Weather Observation Station 4.

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : Find the difference between the total number of CITY entries in the table and the number of distinct CITY entries in the table...

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : Find the difference between the total number of CITY entries in the table and the number of distinct CITY entries in the table...

The PADS | Hackerrank

Author: neptune | 21st-Nov-2022

#SQL #Hackerrank

Problem Statement: Generate the following two result sets: 1. Query an alphabetically ordered list of all names in OCCUPATIONS, immediately followed by the first letter of each profession...

Author: neptune | 21st-Nov-2022

#SQL #Hackerrank

Problem Statement: Generate the following two result sets: 1. Query an alphabetically ordered list of all names in OCCUPATIONS, immediately followed by the first letter of each profession...

6. Solution of Hacker Rank Employee Salaries.

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : Query that prints a list of employee names for employees in Employee having a salary greater than $2000 per month and experience less than 10 months...

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : Query that prints a list of employee names for employees in Employee having a salary greater than $2000 per month and experience less than 10 months...

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...

Identifying the Odd One Out in a Series of Strings | Hackerrank

Author: neptune | 15th-Jun-2023

#Hackerrank #Problem Solving

The article presents an algorithm to identify the odd one out in a series of strings efficiently...

Author: neptune | 15th-Jun-2023

#Hackerrank #Problem Solving

The article presents an algorithm to identify the odd one out in a series of strings efficiently...

2. Solution of Hacker Rank Weather Observation Station 3.

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : Query a list of CITY names from STATION for cities that have an even ID number. Print the results in any order, but exclude duplicates from the answer...

Author: neptune | 23rd-Jan-2023

#SQL #Hackerrank

Problem Statement : Query a list of CITY names from STATION for cities that have an even ID number. Print the results in any order, but exclude duplicates from the answer...

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...

Backspace String Compare using R | Fresco Play

Author: neptune | 05th-Nov-2023

#Hackerrank #Problem Solving

The code implementation in both R and Python solves the "Backspace String Compare" problem using stack data structure...

Author: neptune | 05th-Nov-2023

#Hackerrank #Problem Solving

The code implementation in both R and Python solves the "Backspace String Compare" problem using stack data structure...

Solving the Ice Cream Parlor Problem | Hackerrank

Author: neptune | 04th-Jun-2023

#Hackerrank #Problem Solving

Two friends like to pool their money and go to the ice cream parlour. They always choose two distinct flavours and they spend all of their money...

Author: neptune | 04th-Jun-2023

#Hackerrank #Problem Solving

Two friends like to pool their money and go to the ice cream parlour. They always choose two distinct flavours and they spend all of their money...

Git - Recovering Discarded Changes

Author: neptune | 13th-Jul-2023

#Github #Problem Solving

We will follow a scenario where a developer is working on a web application and needs to recover a discarded commit to reintroduce a specific feature...

Author: neptune | 13th-Jul-2023

#Github #Problem Solving

We will follow a scenario where a developer is working on a web application and needs to recover a discarded commit to reintroduce a specific feature...

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...

Problem of Merging Two Sorted Linked Lists

Author: neptune | 02nd-Jun-2023

#Algorithms #Problem Solving

Merging two sorted linked lists efficiently into a single, sorted list can be achieved using optimized algorithms...

Author: neptune | 02nd-Jun-2023

#Algorithms #Problem Solving

Merging two sorted linked lists efficiently into a single, sorted list can be achieved using optimized algorithms...

Finding the Most Expensive Keyboard and USB Drive within a Budget | Hackerrank

Author: neptune | 05th-Jun-2023

#Hackerrank #Problem Solving

A person wants to determine the most expensive computer keyboard and USB drive that can be purchased with a give budget...

Author: neptune | 05th-Jun-2023

#Hackerrank #Problem Solving

A person wants to determine the most expensive computer keyboard and USB drive that can be purchased with a give budget...

Cassandra Products JSON | Fresco Play

Author: neptune | 29th-Oct-2023

#Hackerrank #Problem Solving

We'll go through a series of common tasks related to managing data in Cassandra...

Author: neptune | 29th-Oct-2023

#Hackerrank #Problem Solving

We'll go through a series of common tasks related to managing data in Cassandra...

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."..

Join Operations in R | Fresco Play

Author: neptune | 29th-Oct-2023

#Hackerrank #Problem Solving

Perform various join operations in R using two data sets, 'flights' and 'weather'...

Author: neptune | 29th-Oct-2023

#Hackerrank #Problem Solving

Perform various join operations in R using two data sets, 'flights' and 'weather'...

View More

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

Awesome!