Python 1711.py
class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
items = defaultdict(int)
for d in deliciousness:
items[d] += 1
high = max(items)
result = 0
for i in items:
for exponent in range(21 + 1): # at most 2^20 per food
two = 1 << exponent
other = two - i
if other > high:
break
if other < i: # don't count twice, (a,b) is considered identical to (b,a)
continue
if other == i:
result += (items[i] - 1) * items[i] // 2 # can't match an ingredient with itself
elif other in items:
result += items[i] * items[other]
return result % 1_000_000_007
Difficulty
and has an acceptance rate of about 33% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Hash Table
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a method that counts unordered pairs of integers whose sum equals a power of two. It first builds a frequency map of the input values, then iterates over each distinct value and checks all possible powers of two up to (2^{21}). For each power, it computes the complementary value needed to reach that sum and updates the result based on the frequencies of the two values. The final count is returned modulo (1{,}000{,}000{,}007).
Building the frequency map
items = defaultdict(int)
for d in deliciousness:
items[d] += 1
A defaultdict of integers is used to tally how many times each distinct integer appears in the input list. This structure enables constant-time look-ups of frequencies later in the algorithm.
Determining the search bound
high = max(items)
The maximum key present in the frequency map is stored. This value serves as an upper bound when searching for a complementary number that would form a valid pair. By knowing the largest possible element, the algorithm can stop early for powers of two that would require a complement larger than any existing value.
Enumerating candidate pairs
result = 0
for i in items:
for exponent in range(21 + 1): # at most 2^20 per food
two = 1 << exponent
other = two - i
if other > high:
break
if other < i: # don't count twice, (a,b) is considered identical to (b,a)
continue
if other == i:
result += (items[i] - 1) * items[i] // 2 # can't match an ingredient with itself
elif other in items:
result += items[i] * items[other]
The outer loop walks through each distinct value i. The inner loop iterates over exponents from 0 to 21, generating the corresponding power of two with a left-shift operation (1 << exponent). The complement other needed to reach that power is computed as two - i.
Early termination
If other exceeds the previously computed high, the inner loop breaks. Since the powers of two increase monotonically, any subsequent exponent would only produce larger complements, making further checks unnecessary. This early exit reduces the number of iterations dramatically for large values of i.
Avoiding double counting
When other is smaller than i, the iteration skips the current combination. Because pairs are unordered, counting only the cases where other is greater than or equal to i guarantees each pair is considered exactly once.
Handling identical elements
If other equals i, the code computes the number of ways to choose two distinct occurrences from the same bucket using the combinatorial formula n · (n-1) / 2. This ensures that an element is never paired with itself in the same position, while still allowing distinct indices that hold the same value to form a valid pair.
Handling distinct elements
When other is different from i and present in the frequency map, the contribution to the result is the product of the two frequencies, items[i] * items[other]. This accounts for every possible pairing between the occurrences of the two values.
Modulo reduction
return result % 1_000_000_007
The accumulated count may exceed the range of standard integers, so the final answer is reduced modulo the large prime (1{,}000{,}000{,}007) before being returned.
Edge-case handling
The algorithm gracefully manages inputs that contain a single distinct value by using the combinatorial branch when other == i. It also correctly processes inputs where no two numbers can sum to a power of two; in such cases the inner conditions never trigger a result increment, and the method returns zero. The early break on other > high ensures that even when the input contains very large numbers, the inner loop does not waste cycles on impossible complements. Additionally, the use of a defaultdict prevents key-error exceptions when accessing frequencies.
Performance optimizations
The frequency map eliminates the need to scan the original list repeatedly, turning repeated value look-ups into constant-time dictionary accesses. Limiting the exponent range to 21 reflects the problem’s constraint that the maximum possible sum does not exceed (2^{21}), thereby bounding the inner loop. The left-shift operation (1 << exponent) is a fast way to compute powers of two without invoking exponentiation functions. Early termination of the inner loop when the complement surpasses the maximum existing value cuts off unnecessary iterations. Finally, the combinatorial shortcut for identical elements avoids nested loops over individual indices, collapsing many potential pairings into a single arithmetic expression.
ELI5 - Simplified Explanation
Imagine a big basket full of yummy snacks, and each snack has a number written on it. The goal is to pick two snacks that add up to a magic number. These magic numbers are always special because they are powers of two, like two, four, eight, sixteen, and so on.
First, the code looks at all the snacks in the basket and lines them up to see how many of each kind there are. It remembers these counts so it doesn't have to search through the whole pile every single time.
Then, the code starts looking through the snacks one by one. For every snack held, it tries to figure out what matching number is needed to make a magic sum. If the current snack is a two, it checks if there is a six nearby to make eight, or a fourteen to make sixteen. It keeps going through these powers of two until the numbers get too big to be possible.
When it finds a match, it counts how many ways those snacks can come together. Special care is taken so that a snack is not paired with itself unless there are two of that exact same snack in the basket. If it finds different kinds of snacks that add up to a magic total, it multiplies how many of each kind exist to find all the possible pairs. All of these pairings are collected into a final count.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||
|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||
| WalkCCC | C++ | Python | Java | |||||
| leetcode.ca | C++ | Python | Java | Go | ||||
| Progiez | C++ | Python | Java | |||||
| github | black-shadows | C++ | ||||||
| charles-wangkai | Java | |||||||
| everthis | JS | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JS | |||||||
| lkwq007 | Python | |||||||
| suxrobGM | C# | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Python, Java | |||||||
| leetcode.ca | C++, Go, Java, Python | |||||||
| Progiez | C++, Java, Python | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JavaScript | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| lkwq007 | Python | |||||||
| suxrobGM | C# |
Videos
Similar Problems
- problem 1679: Max Number of K-Sum Pairs
- problem 2115: Find All Possible Recipes from Given Supplies
Solved On The Same Day
- problem 1184: Distance Between Bus Stops
- problem 1342: Number of Steps to Reduce a Number to Zero
- problem 1399: Count Largest Group
- problem 1496: Path Crossing
- problem 1646: Get Maximum in Generated Array
- problem 1893: Check if All the Integers in a Range Are Covered
- problem 2404: Most Frequent Even Element
- problem 2432: The Employee That Worked on the Longest Task
- problem 2451: Odd String Difference
- problem 2540: Minimum Common Value
- problem 609: Find Duplicate File in System
- problem 1169: Invalid Transactions
- problem 1781: Sum of Beauty of All Substrings
- problem 1865: Finding Pairs With a Certain Sum
- problem 1871: Jump Game VII
- problem 2013: Detect Squares
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality