From Brute Force to Optimal: How to Level Up Your Solutions — A Neo’s Matrix Moment

The Quest Begins (The "Why")

I still remember the first time I hit a wall on a coding challenge. The problem was simple on paper: given an array of integers, count how many pairs (i, j) with i < j have a sum that’s divisible by k. I opened my editor, typed out a double loop, and watched the test cases crawl by. Small inputs passed, but the larger ones timed out like a boss battle where my sword kept breaking. I felt that familiar frustration—why is my solution so slow when the idea is so straightforward?

That moment sparked a quest. I wasn’t just looking for a faster implementation; I wanted to understand the mental shift that turns a brute‑force grind into an elegant, lightning‑fast answer. If you’ve ever stared at a timeout and wondered if there’s a hidden shortcut, you’re in the right place.

The Revelation (The Insight)

The breakthrough didn’t come from memorizing a new algorithm; it came from reframing the problem. Instead of asking “which pairs add up to a multiple of k?” I started asking “what do the individual numbers look like when we look at them modulo k?”

Here’s the aha!: two numbers a and b satisfy (a + b) % k == 0 exactly when their remainders r₁ = a % k and r₂ = b % k add up to k (or both are zero). In other words, we need complementary remainders. If we know how many numbers produce each remainder, we can count the pairs in O(n + k) time—no nested loops required.

It felt like discovering a secret warp pipe in a classic platformer. Suddenly the maze collapsed into a straight line, and the answer was just a matter of counting.

Wielding the Power (Code & Examples

The Brute‑Force Struggle (the “trap” to avoid)

def divisible_sum_pairs_brute(arr, k):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if (arr[i] + arr[j]) % k == 0:
                count += 1
    return count

This works, but it’s O(n²). For n = 10⁵ it’s basically a never‑ending loading screen. The trap here is thinking “the problem is about pairs, so I must examine every pair.”

The Optimal Spell (the “power‑up”)

def divisible_sum_pairs_optimal(arr, k):
    # Frequency of each remainder 0 … k-1
    rem_cnt = [0] * k
    for num in arr:
        rem_cnt[num % k] += 1

    # Pairs where both remainders are 0
    count = rem_cnt[0] * (rem_cnt[0] - 1) // 2

    # If k is even, handle the special middle remainder k/2
    if k % 2 == 0:
        count += rem_cnt[k // 2] * (rem_cnt[k // 2] - 1) // 2
        upper = k // 2 - 1
    else:
        upper = k // 2

    # Pair remainder r with k - r
    for r in range(1, upper + 1):
        count += rem_cnt[r] * rem_cnt[k - r]

    return count

Why this works:

• We first bucket numbers by their remainder when divided by k (O(n)).
• Any two numbers from the same bucket only produce a valid pair if the remainder is 0 or, when k is even, k/2. Those are handled with the combination formula nC2.
• For every other remainder r, we match it with its complement k‑r. Multiplying the frequencies gives the number of cross‑bucket pairs.
• The loop runs at most k/2 times, so the total complexity is O(n + k).

Common pitfalls to watch:

1. Forgetting the special case when k is even (the k/2 remainder pairs with itself).
2. Using integer division incorrectly for the combination formula—make sure you subtract one before dividing by two.
3. Assuming the loop should go up to k; you’ll double‑count pairs if you do.

A Quick Demo

arr = [1, 3, 2, 6, 1, 2]
k = 3
print(divisible_sum_pairs_brute(arr, k))   # 5
print(divisible_sum_pairs_optimal(arr, k)) # 5

Both give the same answer, but the optimal version finishes instantly even when arr has a million elements.

Why This New Power Matters

Shifting from “check every pair” to “count remainders” isn’t just a trick for this one problem—it’s a mindset. Top coders constantly ask: What property of the data can I exploit? Whether it’s sorting, hashing, dynamic programming, or a simple mathematical invariant, the goal is to reduce the problem’s dimensionality.

Once you internalize this, you start seeing patterns everywhere:

• In “two‑sum” you look for complement values.
• In “longest substring without repeating characters” you track the last index of each character.
• In “maximum subarray sum” you keep a running best (Kadane’s).

Each of those is just a different way of saying, “Don’t enumerate; aggregate.”

The payoff? Your solutions scale, your interviewers smile, and you get that rush of turning a seemingly impossible task into a clean, elegant piece of code—like finally landing the perfect combo in a fighting game after hours of practice.

Your Turn

Here’s a challenge to test your new lens: Given an array, find the number of triplets (i, j, k) with i < j < k whose sum is divisible by 3. Try applying the remainder‑frequency idea (now with three numbers) and see if you can beat the naïve O(n³) approach.

Drop your solution or thoughts in the comments—I’d love to see how you level up!

---

Happy coding, and may your algorithms always find the shortcut! 🚀