HackerRank ‘Electronics Shop’ Solution

H
Short Problem Definition:

Monica wants to buy a keyboard and a USB drive from her favorite electronics store. The store has several models of each. Monica wants to spend as much as possible for the 2 items, given her budget.

Given the price lists for the store’s keyboards and USB drives, and Monica’s budget, find and print the amount of money Monica will spend. If she doesn’t have enough money to both a keyboard and a USB drive, print -1 instead. She will buy only the two required items.

Link

Electronics Shop

Complexity:

time complexity is O(N*M)

space complexity is O(1)

Execution:

This is one of the problem specifications that feel like there has to be a better solution. The solution presented here is naive and is O(N*M). Given that this is categorized as easy, I assumed that I can get away with this simple solution.

One could sort one of the arrays and use binary search to find the ideal match, this would result in O(N*log(N)).

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/bin/python
 
def getMoneySpent(keyboards, drives, s):
    spend = -1
    for dr in drives:
        for kb in keyboards:
            cnt = dr+kb
            if cnt <= s and cnt > spend:
                spend = cnt
    return spend
             
s,n,m = raw_input().strip().split(' ')
s,n,m = [int(s),int(n),int(m)]
 
keyboards = map(int, raw_input().strip().split(' '))
drives = map(int, raw_input().strip().split(' '))
 
moneySpent = getMoneySpent(keyboards, drives, s)
print(moneySpent)

About the author

Add comment

Archives

Categories