George went to a shop and is planning to buy food for his family. There are 4 members in his family including himself. And everyone wants to eat something different.
He wants Pizza for himself, his wife just wants salad , his son wants to eat hamburger and his daughter wants to have a burrito for herself.
In the shop there are multiple varieties of each food type, find the number of ways in which George can buy food for each person in the family(same food type as they want) if he has X dollars in his pocket.
Eg:
Prices of each food:
Pizza [1, 4, 5]
Salad [2, 3, 6]
Hamburger [5]
Burrito [6 3 3]
My solution: Sort each list. Find number of ways iterating through each list and doing binary search on the fourth one.
Is there any better solution than this? Thanks.
Constraints: 1 <= x <= 10^9 1 <= size of each list <= 10^3 1 <= price of food item <= 10^9
Meet in the middle. Iterate through all pairs of $$$1$$$ and $$$2$$$ types and write them into one array, and of $$$3$$$ and $$$4$$$ types to another one. Problem then reduced to a classic one — you have two array $$$a$$$ and $$$b$$$, each has size $$$\le 10^6$$$, find the number of pairs $$$(i, j)$$$ such that $$$a_i + b_j \le x$$$.