To solve this problem, we need to count the number of unordered pairs (i, j) such that the sum of the elements at these indices is a power of two.

Approach

1. Frequency Map: First, we create a frequency map to count occurrences of each number in the array. This helps in efficiently checking and counting pairs.
2. Generate Powers of Two: We generate all possible powers of two up to twice the maximum value in the array. This is because the sum of any two elements in the array cannot exceed twice the maximum value.
3. Count Valid Pairs: For each power of two (denoted as S), we check all numbers x in the frequency map. For each x, we compute y = S - x. If y exists in the frequency map:
   • If x == y, the number of valid pairs is the combination of occurrences of x taken 2 at a time.
   • If x != y, the number of valid pairs is the product of occurrences of x and y.
4. Sum Valid Pairs: Sum the valid pairs for all powers of two to get the final result.

Solution Code

from collections import Counter

def count_power_two_pairs(arr):
    if not arr:
        return 0

    freq = Counter(arr)
    max_val = max(arr)
    max_sum = max_val * 2
    total_pairs = 0

    s = 1  # Start with 2^0 = 1
    while s <= max_sum:
        current = 0
        for x in freq:
            if x > s // 2:
                continue
            y = s - x
            if y not in freq:
                continue
            if x == y:
                # Number of ways to choose 2 elements from freq[x]
                current += freq[x] * (freq[x] - 1) // 2
            else:
                current += freq[x] * freq[y]
        total_pairs += current
        s *= 2  # Next power of two

    return total_pairs

# Example usage:
# Input array: [1,2,3,4,5]
# Output should be 2 (1+3=4,3+5=8)
print(count_power_two_pairs([1,2,3,4,5]))  # Output: 2

Explanation

• Frequency Map: The Counter from the collections module is used to count how many times each number appears. This allows O(1) lookups for checking the presence of a number.
• Powers of Two: We generate powers of two by starting from 1 (2^0) and doubling until we exceed twice the maximum value in the array. This ensures we cover all possible sums that could be powers of two.
• Pair Counting: For each power of two S, we check each number x. If x is less than or equal to S/2, we compute y = S - x. If y exists, we count the valid pairs based on whether x and y are the same or different. This avoids double counting pairs (since we only consider x <= y).

This approach efficiently counts the valid pairs with a time complexity of O(n log M), where n is the number of elements in the array and M is twice the maximum value in the array. This is feasible for large input sizes.

Final Answer

The function count_power_two_pairs returns the number of valid pairs. For the example input [1,2,3,4,5], the output is 2.

\boxed{2}

作者声明:本文包含人工智能生成内容。