Introduction

The most natural interpretation of this problem is: find pairs (a, b) in an array such that a % b == k for a given integer k. The condition looks simple, but it hides useful arithmetic structure that can help you move beyond the obvious O(n^2) double loop.

Understanding The Modulo Condition

If a % b == k, then there exists an integer q such that:

a = q * b + k

For positive integers, this immediately tells you two things:

• 'b cannot be 0, because modulo by zero is invalid'
• if b <= k, then a % b cannot equal k

So for each candidate b, the only possible matching values of a are k + b, k + 2b, k + 3b, and so on.

The Brute-Force Solution

If the array is small, the straightforward solution is perfectly fine:

1def find_pairs_bruteforce(arr, k):
2    pairs = []
3    for i, a in enumerate(arr):
4        for j, b in enumerate(arr):
5            if i != j and b != 0 and a % b == k:
6                pairs.append((a, b))
7    return pairs
8
9print(find_pairs_bruteforce([5, 6, 7, 10], 1))

This is easy to read, easy to test, and hard to get wrong. Its cost is O(n^2), which becomes expensive on large arrays.

Using Arithmetic To Skip Impossible Pairs

For positive integers, you can do better by using the structure of the equation. Build a frequency table of the array values. Then, for each candidate b, generate only the a values that could possibly satisfy a % b == k.

1from collections import Counter
2
3
4def find_pairs(arr, k):
5    freq = Counter(arr)
6    max_val = max(arr) if arr else 0
7    pairs = []
8
9    for b in freq:
10        if b == 0 or b <= k:
11            continue
12
13        a = k + b
14        while a <= max_val:
15            if a in freq:
16                pairs.extend((a, b) for _ in range(freq[a] * freq[b]))
17            a += b
18
19    return pairs
20
21print(find_pairs([5, 6, 7, 10], 1))

This does not test every pair. Instead, it jumps over impossible values and only checks arithmetic progressions that can produce the right remainder.

Counting Pairs Instead Of Storing Them

Many interview problems only ask for the count. In that case, returning every pair wastes memory. Counting is usually simpler:

1from collections import Counter
2
3
4def count_pairs(arr, k):
5    freq = Counter(arr)
6    max_val = max(arr) if arr else 0
7    total = 0
8
9    for b, count_b in freq.items():
10        if b == 0 or b <= k:
11            continue
12
13        a = k + b
14        while a <= max_val:
15            total += freq.get(a, 0) * count_b
16            a += b
17
18    return total
19
20print(count_pairs([5, 6, 7, 10], 1))

This is a better choice when the number of valid pairs could be much larger than the array itself.

Defining What Counts As A Pair

Before optimizing, decide exactly what the problem means:

• Are pairs ordered, so (a, b) is different from (b, a)?
• Can the same array element be reused, or must indices be distinct?
• Do duplicates count multiple times?
• Are negative numbers allowed?

These questions matter because modulo is not symmetric and language rules for negative operands differ. In Python, the remainder has the sign of the divisor; in other languages, behavior may differ. If the original array can contain negatives, use a definition that matches the target language rather than assuming mathematics alone will settle it.

When The Brute-Force Version Is The Right Answer

The arithmetic optimization is useful when values are positive and the value range is manageable. If the array is tiny, or if clarity matters more than raw speed, the double loop may still be the better solution. A readable O(n^2) implementation often beats a clever one that nobody trusts.

Optimization should follow the constraints. If n is only a few hundred, the simpler algorithm is often the right engineering choice.

Common Pitfalls

• Forgetting that b cannot be zero.
• Ignoring the fact that b > k is required in the positive-integer case.
• Treating (a, b) and (b, a) as interchangeable even though modulo is directional.
• Counting values instead of indices without checking whether duplicates should produce multiple pairs.
• Applying the positive-integer optimization when the array may contain negatives and the language defines % differently.

Summary

• 'a % b == k implies a = q * b + k for some integer q.'
• The brute-force double loop is the clearest solution for small inputs.
• For positive integers, you can generate only plausible a values for each b.
• Counting matches is often cheaper than returning every pair.
• Always define how zero, negatives, duplicates, and ordering should be handled.