Finding the Most Expensive Keyboard and USB Drive within a Budget | Hackerrank
Author: neptune | 05th-Jun-2023
Problem Statement:
A person wants to determine the most expensive computer keyboard and USB drive that can be purchased with a give budget. Given price lists for keyboards and USB drives and a budget, find the cost to buy them. If it is not possible to buy both items, return -1.
Sample Input:
Keyboards: [40, 50, 60]
Drives: [5, 8, 12]
Budget: 60
Sample Output:
58
Naive Approach
The naive approach involves iterating through all possible combinations of a keyboard and a USB drive, calculating the cost of each combination, and keeping track of the maximum cost that falls within the budget.
Algorithm to Solve Naive Approach:
1. Initialise a variable `max_cost` to -1.
2. Iterate through each keyboard price:
-For each keyboard, iterate through each USB drive price:
-Calculate the cost of the current combination (keyboard price + USB drive price).
-If the cost is less than or equal to the budget and greater than the current maximum cost, update `max_cost`.
3. Return `max_cost`.
Naive Approach Python Code:
def getMoneySpent(keyboards, drives, b):
max_cost = -1 # Variable to store the maximum cost
# Iterate through each keyboard
for keyboard in keyboards:
# Iterate through each USB drive
for drive in drives:
cost = keyboard + drive # Calculate the cost of the current combination
# Check if the cost is within the budget and greater than the current maximum cost
if cost <= b and cost > max_cost:
max_cost = cost
return max_cost
# Testing the function with sample inputs
keyboards = [40, 50, 60]
drives = [5, 8, 12]
budget = 60
print(getMoneySpent(keyboards, drives, budget)) # Output: 58
The naive approach checks all possible combinations of keyboards and USB drives, which leads to a time complexity of O(n^2), where n is the maximum length between the keyboards and drives lists.
Optimised Approach
The optimised approach involves sorting the keyboard prices in descending order and the USB drive prices in ascending order. By doing so, we can use two pointers to traverse the sorted lists simultaneously and find the most expensive combination within the budget efficiently.
Algorithm to Solve Optimised Approach:
1. Sort the keyboard prices in descending order.
2. Sort the USB drive prices in ascending order.
3. Initialise `max_cost` to -1.
4. Initialise two indices `keyboard_index` and `drive_index` to 0.
5. While both `keyboard_index` and `drive_index` are within their respective list lengths:
- Calculate the cost of the current combination (keyboard price + USB drive price).
- If the cost is less than or equal to the budget and greater than the current maximum cost, update `max_cost`.
- Move to the next keyboard or drive based on the comparison with the budget.
6. Return `max_cost`.
Optimised Approach Python Code:
def getMoneySpent(keyboards, drives, b):
keyboards.sort(reverse=True) # Sort the keyboard prices in descending order
drives.sort() # Sort the USB drive prices in ascending order
max_cost = -1 # Variable to store the maximum cost
# Initialise indices for keyboards and drives
keyboard_index = 0
drive_index = 0
# Iterate through the sorted lists
while keyboard_index < len(keyboards) and drive_index < len(drives):
cost = keyboards[keyboard_index] + drives[drive_index]
# Check if the cost is within the budget and greater than the current maximum cost
if cost <= b and cost > max_cost:
max_cost = cost
# Move to the next keyboard or drive based on the comparison
if cost < b:
drive_index += 1
else:
keyboard_index += 1
return max_cost
# Testing the function with sample inputs
keyboards = [40, 50, 60]
drives = [5, 8, 12]
budget = 60
print(getMoneySpent(keyboards, drives, budget)) # Output: 58
The optimised approach sorts the lists, allowing us to efficiently traverse them using two pointers. This results in a time complexity of O(n log n), where n is the maximum length between the keyboards and drives lists, due to the sorting step.
By using the optimised approach, we can find the most expensive combination of a keyboard and USB drive within the given budget efficiently.
#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
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...
The Blunder | HackerrankAuthor: 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 ReportAuthor: 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...
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...
The PADS | HackerrankAuthor: 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...
Identifying the Odd One Out in a Series of Strings | HackerrankAuthor: neptune | 15th-Jun-2023
#Hackerrank #Problem Solving
The article presents an algorithm to identify the odd one out in a series of strings efficiently...
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...
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...
Modified 0-1 knapsack problem | Frsco Play HackerrankAuthor: neptune | 05th-Nov-2023
#Hackerrank #Problem Solving
An automobile mechanic wants to buy a set of spare parts from a manufacturing unit. Goal is to maximise the amount of money the mechanic can earn...
AngularJS - Know Tech Frameworks | Fresco PlayAuthor: 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...
Solving the Ice Cream Parlor Problem | HackerrankAuthor: 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...
Backspace String Compare using R | Fresco PlayAuthor: 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...
Git - Recovering Discarded ChangesAuthor: 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 HackerrankAuthor: 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 ListsAuthor: neptune | 02nd-Jun-2023
#Algorithms #Problem Solving
Merging two sorted linked lists efficiently into a single, sorted list can be achieved using optimized algorithms...
Cassandra Products JSON | Fresco PlayAuthor: 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 | HackerrankAuthor: 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 PlayAuthor: neptune | 29th-Oct-2023
#Hackerrank #Problem Solving
Perform various join operations in R using two data sets, 'flights' and 'weather'...
View More