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

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.