Problem 1711

Abstract / Summary

Count the number of ways to pick three different food items from a list to make a good meal.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
23 lines | 838 bytes | submitted December 12, 2023 | GitHub   15% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 33% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Hash Table
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.30 | σ = 1.12

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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#
22 links | 12 authors | 7 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

17 solutions   December 12, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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