Enumeration Coding Problems: 13 Questions with Solutions

How enumeration works, step by step

1. Count the pairs whose sum is divisible by 3 by trying every pair i < j: i fixes the first number and j runs over everything after it. With 5 numbers that is 5 × 4 / 2 = 10 pairs, one cell each in the grid.
2. i = 0, j = 1: 2 + 7 = 9, which is divisible by 3, so this pair counts and count = 1.
3. i = 0, j = 2: 2 + 4 = 6, which is divisible by 3, so this pair counts and count = 2.
4. i = 0, j = 3: 2 + 5 = 7 leaves remainder 1 when divided by 3, so it does not count.
5. i = 0, j = 4: 2 + 3 = 5 leaves remainder 2 when divided by 3, so it does not count.
6. i moves on to 1 and j restarts just after it. i = 1, j = 2: 7 + 4 = 11 leaves remainder 2 when divided by 3, so it does not count.
7. i = 1, j = 3: 7 + 5 = 12, which is divisible by 3, so this pair counts and count = 3.
8. i = 1, j = 4: 7 + 3 = 10 leaves remainder 1 when divided by 3, so it does not count.
9. i moves on to 2 and j restarts just after it. i = 2, j = 3: 4 + 5 = 9, which is divisible by 3, so this pair counts and count = 4.
10. i = 2, j = 4: 4 + 3 = 7 leaves remainder 1 when divided by 3, so it does not count.
11. i moves on to 3 and j restarts just after it. i = 3, j = 4: 5 + 3 = 8 leaves remainder 2 when divided by 3, so it does not count.
12. All 10 pairs are checked, and 4 have a sum divisible by 3: (2, 7), (2, 4), (7, 5) and (4, 5). Two nested loops make it O(n²) time — fine for small inputs, and the baseline any faster idea must beat.

Enumeration study plan

7 of the 13 Enumeration problems (4 easy and 3 medium) over 3 days, about 3 h 20 min in all — the pattern first, then easiest to hardest. After that, the other 6 in the full list below are practice at your own pace. Then move on to Intervals.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Count Good Triplets Easy
• Count Square Sum Triples Easy
• Number of Arithmetic Triplets Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Count Symmetric Integers Easy
• Reordered Power of 2 Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Count Number of Maximum Bitwise-OR Subsets Medium
• Find the Integer Added to Array II Medium

Next topic: Intervals

Enumeration: the essentials

When to reach for it

The limits are small enough to count the work in advance: n ≤ 100 allows every triple (about 1.6 × 10⁵ for n = 100), n ≤ 20 every subset (about a million), and values up to 10⁴ allow trying every candidate answer. "Count the triplets that satisfy…", "how many integers in [low, high] are symmetric" and "can these digits be rearranged into a power of two" are meant to be enumerated — over the right set.

The pattern

Estimate first: candidates × cost of checking each should stay around 10⁷–10⁸ simple steps. Then choose what to enumerate, usually the smaller side. Reordered Power of 2 does not try the orderings of n's digits (up to 10! ≈ 3.6 million); it compares digit counts with the 31 powers of two below 2³¹. Generate each candidate once: start j at i + 1, not at 0.

from collections import Counter

def reordered_power_of_2(n):
    digits = Counter(str(n))
    return any(Counter(str(1 << k)) == digits for k in range(31))

Cost

Exactly the number of candidates times the cost of each check: O(n³) for triples, O(2ⁿ × n) for subsets, O(range × digits) for a numeric range. An early exit improves the constant; choosing what to enumerate changes the bound.

Common mistakes

• Counting one combination several times by starting every loop at index 0.
• Enumerating the larger of two equivalent sets, such as the digit orderings rather than the targets.
• Skipping the estimate: with n = 10⁴, an O(n³) loop is 10¹² steps.
• An off-by-one at either end of an inclusive range [low, high].

Start with

• Count Good Triplets: every triple, checked directly.
• Count Square Sum Triples: enumerating two values, deriving the third.
• Reordered Power of 2: enumerating the targets instead.

All enumeration problems

Easy (10)

• Form Smallest Number From Two Digit Arrays Array, Hash Table
• Count the Number of Incremovable Subarrays I Array, Two Pointers
• Maximum Height of a Triangle Array, Greedy, Simulation
• Binary Watch Bit Manipulation, Backtracking
• Find the Peaks Array
• Number of Common Factors Math, Number Theory
• Count Symmetric Integers Math
• Count Square Sum Triples Math
• Number of Arithmetic Triplets Array, Hash Table, Two Pointers
• Count Good Triplets Array

Medium (3)

• Find the Integer Added to Array II Array, Two Pointers, Sorting
• Count Number of Maximum Bitwise-OR Subsets Bit Manipulation, Backtracking
• Reordered Power of 2 Math, Counting

Companies that ask enumeration problems

• Amazon 12 problems on enumeration
• Google 6 problems on enumeration
• Adobe 5 problems on enumeration
• Accenture 2 problems on enumeration
• Infosys 2 problems on enumeration
• TCS 2 problems on enumeration
• Capgemini 1 problem on enumeration
• Oracle 1 problem on enumeration
• Samsung 1 problem on enumeration
• Wipro 1 problem on enumeration

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems