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.
time complexity is O(N*M)
space complexity is O(1)
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)).
#!/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)
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.