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.