💡 Problem Formulation: We need to write a program in Python that can take an input list of integers and return the number of index pairs whose corresponding element sums equal a power of 2. For example, given the input list [1, 3, 5, 7, 9], the program should identify pairs like (0, 1) where the sum of elements at these indices (1+3) is a power of two, i.e., 4.
Method 1: Brute Force
This method involves checking all possible pairs in the list and verifying if their sum is a power of two using a helper function. This is not the most efficient approach due to its O(n^2) complexity, but it’s a straightforward solution.
Here’s an example:
def is_power_of_two(n):
return n and (not(n & (n - 1)))
def count_pairs(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i+1, n):
if is_power_of_two(nums[i] + nums[j]):
count += 1
return count
print(count_pairs([1, 3, 5, 7, 9]))Output: 1
The code snippet defines a function is_power_of_two that determines whether a number is a power of two. The count_pairs function counts all unique pairs in the list whose sum is a power of two. The nested for-loops generate all possible index pairs.
Method 2: Optimization Using Set
To reduce the time complexity, we can use a set to check if the complement of the current element (a power of two minus the element) exists in the list. This method reduces the time complexity to O(n*log(n)), since checking for membership in a set is O(1) and we have to find powers of two up to a log(n) value.
Here’s an example:
def count_pairs(nums):
count = 0
num_set = set(nums)
max_num = 2 ** int(log(max(nums)*2, 2))
for num in nums:
power = 1
while power <= max_num:
if (power - num) in num_set and (power - num) != num:
count += 1
power *= 2
return count // 2 # Divide by 2 to adjust for double counting
from math import log
print(count_pairs([1, 3, 5, 7, 9]))Output: 1
The count_pairs function uses a set to store the list elements which allows for constant time membership checks. We only iterate through the list and check for powers of two up until double the largest number in the list.
Method 3: Sorting and Two Pointers
This method initially sorts the list, then uses two pointers to find pairs that sum up to a power of two. One pointer starts from the beginning and the other from the end of the sorted list. Depending on the sum, either the left or right pointer is moved. This method offers O(n*log(n)) complexity due to sorting.
Here’s an example:
def is_power_of_two(x):
return x and (not(x & (x - 1)))
def count_pairs(nums):
nums.sort()
count = 0
left, right = 0, len(nums) - 1
while left < right:
curr_sum = nums[left] + nums[right]
if is_power_of_two(curr_sum):
count += 1
left += 1
right -= 1
elif curr_sum < 2 ** int(log(curr_sum, 2)):
left += 1
else:
right -= 1
return count
from math import log
print(count_pairs([1, 3, 5, 7, 9]))Output: 1
The count_pairs function sorts the array and then uses a two-pointer approach to find pairs that sum up to a power of two, increasing efficiency over brute force by reducing the number of comparisons.
Method 4: Using Bit Manipulation
This method leverages bit manipulation to quickly check if a sum is a power of two without using the logarithm or division operations, which can be more efficient for certain data sizes and distributions.
Here’s an example:
def count_pairs(nums):
count = 0
for i in range(len(nums)):
for j in range(i+1, len(nums)):
sum = nums[i] + nums[j]
if (sum & (sum - 1)) == 0:
count += 1
return count
print(count_pairs([1, 3, 5, 7, 9]))Output: 1
The code uses a nested for-loop to generate index pairs and utilizes bitwise AND operation to check if the sum of the elements at those indices is indeed a power of two, as powers of two have only one bit set in their binary representation.
Bonus One-Liner Method 5: List Comprehensions and Functions
A compact solution using list comprehensions and functions. This one-liner combines the identification of power of two and pair counting in a single expression, showcasing the expressiveness of Python.
Here’s an example:
def is_power_of_two(x):
return (x != 0) and x & (x - 1) == 0
print(sum(1 for i in range(len(nums)) for j in range(i+1, len(nums)) if is_power_of_two(nums[i] + nums[j])))Output: 1
This one-liner uses a nested list comprehension along with the sum function to count the number of pairs directly. It executes the is_power_of_two function for each unique pair found in the list.
Summary/Discussion
- Method 1: Brute Force. Simple and easy to understand. Not efficient for large datasets due to O(n^2) complexity.
- Method 2: Optimization Using Set. More efficient than brute force. Reduced complexity to O(n*log(n)), but still has overhead due to use of set and looping for power of two check.
- Method 3: Sorting and Two Pointers. Improved efficiency due to sorting. Works well with unique elements, but may miss some pairs if the list contains duplicates.
- Method 4: Using Bit Manipulation. Fastest for bit-wise operations. Potentially more efficient than other methods for certain input patterns, but may be less intuitive to some programmers.
- Bonus One-Liner Method 5: List Comprehensions and Functions. Concise and elegant, utilizing Python’s expressive capabilities. Can be less readable for those not familiar with Python’s list comprehensions.