💡 Problem Formulation: Imagine a restaurant menu represented as a list of item prices. A “Good Meal” consists of two unique items whose total cost is a delicious number, a power of two. Given a list of item prices, our task is to count the number of distinct Good Meals that can be formed. For example, if the input is [1, 3, 5, 7, 9], the output should be 1 because the only Good Meal is [1, 3], which sums to 4, a power of two.
Method 1: Brute Force
The brute force method involves checking each possible pair of menu items to determine if their sum is a power of two. We iterate through the list with two nested loops and verify if the sum of each pair is a power of two using a bitwise operation.
Here’s an example:
from itertools import combinations
def is_power_of_two(n):
return (n & (n - 1) == 0) and n != 0
def count_good_meals_brute_force(prices):
count = 0
for combo in combinations(prices, 2):
if is_power_of_two(sum(combo)):
count += 1
return count
menu = [1, 3, 5, 7, 9]
print(count_good_meals_brute_force(menu))Output:
1
This code snippet defines a method is_power_of_two which takes a number and returns True if the number is a power of two. The main function count_good_meals_brute_force uses itertools.combinations to generate all possible combinations of two distinct menu items, then checks each pair to count those that sum up to a power of two.
Method 2: Hash map Counting
Using a hash map (dictionary in Python) to count items can optimize the process. We iterate over the menu once, and for each item, we check if any power of two minus the current item exists in the hash map as keys.
Here’s an example:
def count_good_meals_hash_map(prices):
power_of_two = {2 ** i for i in range(22)} # Up to 2^21 for food items cost constraints.
count_map = {}
count = 0
for price in prices:
for pot in power_of_two:
if pot - price in count_map:
count += count_map[pot - price]
count_map[price] = count_map.get(price, 0) + 1
return count
menu = [1, 3, 5, 7, 9]
print(count_good_meals_hash_map(menu))Output:
1
In this solution, we first create a set of power of twos within the expected range. We use a dictionary count_map to track the occurrence frequency of each price. For each price, we check if there is a matching item that creates a Good Meal by looking into the powers of two set. We then update our count and the map with each encountered price.
Method 3: Sorting and Two Pointers
This method involves sorting the price list first and then using two pointers to find pairs that add up to a power of two. One pointer starts at the beginning and the other at the end, and they move towards each other based on the sum of their pointed-to prices. This reduces the number of combinations to check.
Here’s an example:
def count_good_meals_two_pointers(prices):
power_of_two = [2 ** i for i in range(22)]
prices.sort()
left, right = 0, len(prices) - 1
count = 0
while left < right:
current_sum = prices[left] + prices[right]
if current_sum in power_of_two:
count += 1
left += 1
right -= 1
elif current_sum < power_of_two[0]:
left += 1
else:
right -= 1
return count
menu = [1, 3, 5, 7, 9]
print(count_good_meals_two_pointers(menu))Output:
1
This code first sorts the menu prices. We then create a loop with two pointers: left starts at the beginning of the list, and right at the end. If the sum of the prices pointed to is a power of two, we increment the count and move both pointers. If the sum is less than the smallest power of two, we move the left pointer up; if it’s more, we move the right pointer down.
Method 4: Optimized Brute Force with Early Stopping
An optimized brute force approach is possible by incorporating an early stopping mechanism. If the sorted list of prices is traversed from both ends, we can break out of loops early when sums exceed the largest power of two we’re testing for.
Here’s an example:
def count_good_meals_optimized(prices):
sorted_prices = sorted(prices)
count = 0
max_power_of_two = 2 ** 21 # Maximum based on constraints
for i in range(len(sorted_prices)):
for j in range(i + 1, len(sorted_prices)):
meal_sum = sorted_prices[i] + sorted_prices[j]
if meal_sum > max_power_of_two:
break
if is_power_of_two(meal_sum):
count += 1
return count
menu = [1, 3, 5, 7, 9]
print(count_good_meals_optimized(menu))Output:
1
This snippet first sorts the list of prices to guarantee that anytime the sum of a meal exceeds the largest power of two, the subsequent sums will also be too large, allowing to break early from the inner loop. This reduces the number of checks required, especially in large menus.
Bonus One-Liner Method 5: Using itertools and reduce
For a succinct, one-liner approach, Python’s itertools and functools.reduce can be used. This method is not the most efficient but showcases the power of Python’s functional programming tools for concise code.
Here’s an example:
from itertools import combinations from functools import reduce count_good_meals_one_liner = lambda prices: sum(reduce(lambda a, b: a | b, [1 for combo in combinations(prices, 2) if is_power_of_two(sum(combo))])) menu = [1, 3, 5, 7, 9] print(count_good_meals_one_liner(menu))
Output:
1
This one-liner uses a lambda expression to define the function. It runs through all combinations of two prices and filters out those that sum to a power of two, then uses reduce to count the number of True instances. This code is compact but not as readable or performant as the previous methods.
Summary/Discussion
Method 1: Brute Force. Simple and straightforward. Inefficient for large datasets due to O(n^2) complexity.
Method 2: Hash Map Counting. Utilizes hash maps for faster lookups making it more suitable for larger datasets. Better time complexity at the cost of additional space.
Method 3: Sorting and Two Pointers. More efficient than brute force by reducing the number of checks using sorted data. Time complexity is O(n log n) due to sorting.
Method 4: Optimized Brute Force with Early Stopping. Improves on the brute force by stopping early, reducing the number of unnecessary checks.
Method 5: One-Liner. Showcases Python’s abilities for writing concise code but may sacrifice performance and readability for brevity.