How to Read Constraints and Immediately Know the Algorithm: A Zelda's Treasure Map

The Quest Begins (The "Why")

I still remember the first time I stared at a competitive‑programming problem and felt my brain short‑circuit. The statement read something like:

“You have an array of length n (1 ≤ n ≤ 2·10⁵). Each element aᵢ satisfies 0 ≤ aᵢ ≤ 10⁹. Find the number of pairs (i, j) with i < j such that aᵢ + aⱼ is a power of two.”

Honestly, my first instinct was to brute‑force every pair – O(n²) – and watch the time limit explode like a boss with too many hit points. I spent an hour tweaking loops, trying to prune, and ended up feeling like Link stuck in a dungeon with no map.

The frustration was real, but it also sparked a question: What if the constraints themselves were whispering the right algorithm?

The Revelation (The Insight)

Here’s the shift that changed everything for me: constraints aren’t just limits; they’re clues. When you see a bound like n ≤ 2·10⁵, the problem designer is practically shouting, “You can afford O(n log n) or O(n √max) but definitely not O(n²).” When you see the value range (0 ≤ aᵢ ≤ 10⁹), you start thinking about bit‑wise properties or frequency tables because the universe of possible values is huge but structured.

The breakthrough moment for that power‑of‑two pairs problem came when I realized:

• The sum of two numbers being a power of two means the sum has exactly one bit set.
• For any aᵢ, the only numbers that can pair with it to make a power of two are those equal to (2ᵏ − aᵢ) for some k.
• Since aᵢ ≤ 10⁹, the largest relevant power of two is just above 2·10⁹ → 2³¹ (≈2.147 billion). So we only need to check k = 0 … 31.

That’s it! For each element we look up how many previous elements equal the needed complement for each of the 32 possible powers of two. A simple hash map (or frequency array) gives us O(n · log MAX) time, which is essentially O(n) because log MAX is a tiny constant (32).

It felt like finding the One Ring — suddenly the path lit up, and the monster (the O(n²) trap) shrank to a harmless critter.

Wielding the Power (Code & Examples)

The Struggle (What NOT to do)

# ❌ O(n²) brute force – will TLE on max input
def count_pairs_bruteforce(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            s = arr[i] + arr[j]
            # check if s is power of two
            if s & (s-1) == 0:
                ans += 1
    return ans

The Victory (The insight‑driven solution)

from collections import defaultdict

def count_powers_of_two_pairs(arr):
    freq = defaultdict(int)   # how many times we've seen each value so far
    ans = 0
    # pre‑compute all relevant powers of two (up to 2^31 > 2*10^9)
    powers = [1 << k for k in range(0, 32)]   # 2^0 … 2^31

    for x in arr:
        for p in powers:
            need = p - x
            if need < 0:          # powers are increasing; further p will only be larger
                break
            ans += freq.get(need, 0)
        freq[x] += 1
    return ans

Why this works:

• For each current element x, we ask: “Which earlier values would make a power of two with x?”
• The answer is need = 2ᵏ – x. We simply look up how many times we’ve already seen need.
• The inner loop runs at most 32 times → effectively constant.

Common Traps to Avoid

1. Forgetting the need < 0 break – If you let the loop run through all powers even when need becomes negative, you’ll waste time (still O(32) but unnecessary) and, more importantly, you might start counting pairs with negative numbers that never exist in the input.
2. Using a list for frequencies when values are sparse – Since aᵢ can be up to 10⁹, a plain list of that size would blow memory. A hash map (defaultdict) keeps memory proportional to n, not the value range.

Why This New Power Matters

Once you train yourself to read constraints as hints, problem‑solving stops feeling like guesswork and starts feeling like decoding a designer’s note. You’ll start spotting patterns:

• Small n (≤ 10³) → O(n²) might be fine.
• Large n but small value range → counting sort or frequency array.
• Large value range but small *n* → sort + two‑pointer or binary search.
• Modulo or bit‑wise constraints → think about properties of numbers modulo something or bit tricks.

This mindset has helped me knock out medium‑hard problems in minutes instead of hours, and it’s made interviews feel less like a gauntlet and more like a conversation where I can show the interviewer I see the structure behind the words.

Your Turn

Pick any recent problem you’ve struggled with. Write down the explicit constraints (time limits, input sizes, value ranges) on a scrap piece of paper. Ask yourself:

• What does the size of n tell me about allowable complexity?
• Does the range of values suggest a frequency table, sorting, or bit manipulation?
• Are there any hidden patterns like powers of two, primes, or sums that the limits hint at?

Try to map those observations to an algorithm before you even look at the editorial. If you get stuck, come back and share what you noticed—I’d love to hear your “aha!” moments!

Happy hacking, and may your constraints always guide you to the right treasure. 🚀