3890. Integers With Multiple Sum of Two Cubes

MediumHash TableCountingEnumerationSorting

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

An integer x is called good if it can be written as the sum of two positive cubes in at least two different ways. More precisely, x is good if there exist at least two distinct pairs (a, b) satisfying all of the following:

a and b are positive integers.
a <= b (each pair is ordered so that we don't count (a, b) and (b, a) separately).
x = a³ + b³.

In other words, you need to find numbers that have two or more representations as a sum of two cubes. Such numbers are sometimes known as taxicab-like numbers (the smallest example is 1729 = 1³ + 12³ = 9³ + 10³).

Your task is to return an array containing all good integers that are less than or equal to n, sorted in ascending order.

Example walkthrough of the condition:

For a number like 1729, there are two valid pairs:
- (1, 12) because 1³ + 12³ = 1 + 1728 = 1729
- (9, 10) because 9³ + 10³ = 729 + 1000 = 1729
Since there are at least two distinct pairs, 1729 is a good integer. If n >= 1729, it should appear in the output.

The key points to keep in mind:

Each pair must use positive integers (so a, b >= 1).
Pairs are counted with the constraint a <= b, which guarantees that each unordered pair is only counted once.
You must collect every good integer up to and including n, and the final result must be sorted in ascending order.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Uses a hash map to count how many ways each sum of two cubes can be formed, then filters values with multiple representations.

Open in Flowchart

Intuition

The first thing to notice is that the problem may give us many queries, each asking for all good integers up to some n. Recomputing the good integers from scratch for every query would waste a lot of effort, because the set of good integers never changes — only the cutoff n changes. This hints that we should precompute all possible good integers once, and then answer each query quickly.

The next question is: how large can a and b get? Since each query n is bounded (here by 10⁹), we don't need to consider arbitrarily large cubes. If a³ + b³ already exceeds the maximum possible n, that value can never be part of any answer, so we can safely ignore it. Solving a³ <= 10⁹ gives a <= 1000. That means we only ever need to look at pairs where 1 <= a <= b <= 1000. This keeps the search space small and finite.

With that bound in place, the idea becomes straightforward. We enumerate every pair (a, b) with a <= b, compute x = a³ + b³, and count how many times each value of x appears. A value that appears two or more times means it can be formed by two or more distinct pairs of cubes — exactly the definition of a good integer. Using a hash map keyed by x lets us tally these counts efficiently, and the a <= b ordering ensures each unordered pair is counted only once, so the counts are accurate.

A small but useful optimization while enumerating: for a fixed a, as b increases, x = a³ + b³ only grows. So the moment x exceeds our limit, we can break out of the inner loop instead of continuing — every later b would only make x larger.

Once all counts are gathered, we filter out the values that occurred more than once and sort them in ascending order into a single list GOOD. Now answering any query is simple: since GOOD is sorted, finding all good integers <= n is just a matter of locating the boundary position with binary search and returning everything before it. This turns each query into a fast O(log m) lookup (where m is the number of good integers), rather than a fresh recomputation.

Pattern Learn more about Sorting patterns.

Solution Approach

Solution 1: Preprocessing + Binary Search

The implementation follows two phases: a one-time preprocessing step that builds the list of all good integers, and a per-query step that uses binary search to slice off the part we need.

Step 1: Precompute the cubes.

Since we established that a and b never need to exceed 1000, we first precompute all the cube values to avoid recomputing i³ repeatedly inside the loop:

cubes = [i**3 for i in range(1001)]

Now cubes[i] gives us i³ in constant time.

Step 2: Count how many times each sum appears.

We use a hash map (defaultdict(int)) named cnt where the key is a value x = a³ + b³ and the value is the number of distinct pairs producing it. We enumerate every pair (a, b) with 1 <= a <= b <= 1000. The constraint b starting from a enforces a <= b, so each unordered pair is counted exactly once:

for a in range(1, 1001):
    for b in range(a, 1001):
        x = cubes[a] + cubes[b]
        if x > LIMIT:
            break
        cnt[x] += 1

The key optimization here is the early break: for a fixed a, the value x grows as b increases, so once x > LIMIT (where LIMIT = 10⁹), every larger b is also out of range. Breaking immediately saves unnecessary iterations.

Step 3: Filter and sort the good integers.

A value is good if it was produced by two or more distinct pairs, i.e., its count is greater than 1. We collect all such values and sort them in ascending order into the global list GOOD:

GOOD = sorted(x for x, v in cnt.items() if v > 1)

This list is computed only once and reused across all queries.

Step 4: Answer each query with binary search.

Because GOOD is already sorted, finding all good integers <= n reduces to locating the boundary. We use bisect_right(GOOD, n), which returns the index idx of the first element strictly greater than n. Everything before that index is exactly the set of good integers not exceeding n:

class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        idx = bisect_right(GOOD, n)
        return GOOD[:idx]

Complexity Analysis:

Preprocessing time: O(M²) where M = 1000, since we iterate over all pairs (a, b). This happens only once.
Per-query time: O(log K + idx), where K is the size of GOOD. The bisect_right call is O(log K), and slicing the result takes time proportional to the number of returned elements idx.
Space: O(K) for storing the GOOD list (plus the temporary cnt map during preprocessing).

The core patterns used are hash-map counting to detect values with multiple representations, monotonicity-based pruning (the early break), and binary search on a sorted array to serve queries efficiently.

Example Walkthrough

Let's trace through the solution with a small example using n = 1800. To keep the numbers manageable, we'll restrict our cube search to a, b in the range [1, 12] (since 12³ = 1728, this is enough to discover our target).

Step 1: Precompute the cubes.

We build cubes[i] = i³:

`i`	1	2	3	4	5	6	7	8	9	10	11	12
`i³`	1	8	27	64	125	216	343	512	729	1000	1331	1728

Step 2: Count how many times each sum appears.

We enumerate every pair (a, b) with a <= b, compute x = a³ + b³, and tally counts in cnt. The early break skips sums above our limit. Here are a few representative pairs that lead to our target value:

(1, 12) → 1 + 1728 = 1729 → cnt[1729] = 1
(9, 10) → 729 + 1000 = 1729 → cnt[1729] = 2 ← appears a second time!

Other pairs produce sums like:

(1, 1) → 2 → cnt[2] = 1
(2, 3) → 8 + 27 = 35 → cnt[35] = 1
(5, 6) → 125 + 216 = 341 → cnt[341] = 1

Most sums are reached by only one pair, so their count stays at 1. The value 1729 is special: both (1, 12) and (9, 10) map to it, pushing its count to 2.

A look at the relevant part of cnt after the loop:

`x`	count
2	1
35	1
341	1
...	...
1729	2
...	...

Step 3: Filter and sort the good integers.

We keep only the values whose count is > 1:

GOOD = sorted(x for x, v in cnt.items() if v > 1)
     = [1729]

1729 is the only value in this small range hit by two distinct cube pairs, so it is the sole good integer.

Step 4: Answer the query with binary search.

For the query n = 1800:

idx = bisect_right(GOOD, 1800)   # GOOD = [1729]

bisect_right finds the first position strictly greater than 1800. Since 1729 <= 1800, that boundary is index 1. We return GOOD[:1]:

[1729]

Quick sanity check with a different query:

If n = 1700: bisect_right([1729], 1700) = 0, so we return GOOD[:0] = [] — correct, since 1729 > 1700.
If n = 1729: bisect_right([1729], 1729) = 1 (right-inclusive), so we return [1729] — correct, since 1729 <= 1729.

This illustrates the full pipeline: cubes are precomputed once, each sum's multiplicity is counted via a hash map (with a <= b guaranteeing no double-counting), good values are filtered and sorted a single time, and each query becomes a fast binary-search slice over the prebuilt GOOD list.

Solution Implementation

1from collections import defaultdict
2from bisect import bisect_right
3
4# Upper bound for the values we care about (inclusive).
5LIMIT = 10 ** 9
6
7# Precompute cubes for 0..1000 so we can look them up in O(1).
8# 1000**3 == 10**9, so this range fully covers our LIMIT.
9CUBES = [i ** 3 for i in range(1001)]
10
11# Count how many distinct (a, b) pairs (with a <= b) sum to each value.
12# Key: sum of two cubes, Value: number of ways to form that sum.
13sum_count = defaultdict(int)
14
15for a in range(1, 1001):
16    for b in range(a, 1001):
17        cube_sum = CUBES[a] + CUBES[b]
18        # Pairs are generated with b increasing, so once we exceed LIMIT
19        # all further b for this a will also exceed it -> break early.
20        if cube_sum > LIMIT:
21            break
22        sum_count[cube_sum] += 1
23
24# A "good" integer is one expressible as a sum of two cubes in more than
25# one way (i.e. count > 1). Sort them so we can binary-search by upper bound.
26GOOD_INTEGERS = sorted(value for value, count in sum_count.items() if count > 1)
27
28
29class Solution:
30    def findGoodIntegers(self, n: int) -> list[int]:
31        # Find the rightmost position where GOOD_INTEGERS[i] <= n,
32        # then return every good integer up to (and including) n.
33        idx = bisect_right(GOOD_INTEGERS, n)
34        return GOOD_INTEGERS[:idx]
35

1class Solution {
2    // Upper bound for the values we precompute (10^9).
3    private static final int LIMIT = (int) 1e9;
4
5    // Sorted list of "good" integers: numbers expressible as a sum of two cubes
6    // in more than one distinct way (a Taxicab-like property).
7    private static final List<Integer> goodIntegers = new ArrayList<>();
8
9    static {
10        // Maps each sum-of-two-cubes value to the number of distinct (a, b) pairs
11        // that produce it (with a <= b).
12        Map<Integer, Integer> countMap = new HashMap<>();
13
14        // Precompute cubes for 0..1000 to avoid repeated multiplication.
15        int[] cubes = new int[1001];
16        for (int i = 0; i <= 1000; i++) {
17            cubes[i] = i * i * i;
18        }
19
20        // Enumerate all pairs (a, b) with 1 <= a <= b <= 1000.
21        for (int a = 1; a <= 1000; a++) {
22            for (int b = a; b <= 1000; b++) {
23                int sum = cubes[a] + cubes[b];
24                // Since b grows, the sum only increases; stop once it exceeds the limit.
25                if (sum > LIMIT) {
26                    break;
27                }
28                // Record one more representation for this sum.
29                countMap.merge(sum, 1, Integer::sum);
30            }
31        }
32
33        // A value is "good" if it can be written as a sum of two cubes
34        // in at least two distinct ways.
35        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
36            if (entry.getValue() > 1) {
37                goodIntegers.add(entry.getKey());
38            }
39        }
40
41        // Sort so we can binary search later.
42        Collections.sort(goodIntegers);
43    }
44
45    public List<Integer> findGoodIntegers(int n) {
46        // Find the insertion point for (n + 1); this gives the count of good
47        // integers that are <= n.
48        int index = Collections.binarySearch(goodIntegers, n + 1);
49        if (index < 0) {
50            // binarySearch returns -(insertionPoint) - 1 when not found.
51            index = -index - 1;
52        }
53        // Return all good integers up to and including n.
54        return goodIntegers.subList(0, index);
55    }
56}
57

1// Precomputed list of all "good" integers (Taxicab-like numbers).
2// A number is considered "good" if it can be expressed as the sum of two
3// positive cubes (a^3 + b^3) in more than one distinct way.
4vector<int> good;
5
6// This lambda runs once at program startup to populate the `good` vector.
7// The assignment to `init` ensures the lambda is invoked immediately.
8auto init = [] {
9    const int kLimit = 1e9;  // Upper bound on the values we care about.
10
11    // Maps a sum-of-two-cubes value to the number of ways it can be formed.
12    unordered_map<int, int> count;
13
14    // Precompute cubes for all bases from 0 to 1000.
15    // (1000^3 == 1e9, so we never need a base larger than 1000.)
16    vector<int> cubes(1001);
17    for (int i = 0; i <= 1000; ++i) {
18        cubes[i] = i * i * i;
19    }
20
21    // Enumerate every unordered pair (a, b) with 1 <= a <= b <= 1000
22    // and accumulate how many pairs produce each sum.
23    for (int a = 1; a <= 1000; ++a) {
24        for (int b = a; b <= 1000; ++b) {
25            int sum = cubes[a] + cubes[b];
26            // Since `b` only increases, once the sum exceeds the limit
27            // all further `b` values for this `a` will too, so break early.
28            if (sum > kLimit) break;
29            ++count[sum];
30        }
31    }
32
33    // A value is "good" if at least two distinct pairs produce it.
34    for (const auto& [value, ways] : count) {
35        if (ways > 1) {
36            good.push_back(value);
37        }
38    }
39
40    // Keep the results sorted so we can binary-search them later.
41    sort(good.begin(), good.end());
42
43    return 0;
44}();
45
46class Solution {
47public:
48    // Returns all good integers that are <= n, in ascending order.
49    vector<int> findGoodIntegers(int n) {
50        // Find the first index whose value is strictly greater than n.
51        int idx = upper_bound(good.begin(), good.end(), n) - good.begin();
52        // Everything before that index satisfies value <= n.
53        return vector<int>(good.begin(), good.begin() + idx);
54    }
55};
56

1// Upper bound for the sum-of-two-cubes values we care about.
2const LIMIT = 1e9;
3
4/**
5 * Precomputed, sorted list of "good" integers.
6 *
7 * A "good" integer is a value that can be expressed as the sum of two cubes
8 * (a^3 + b^3 with 1 <= a <= b <= 1000) in more than one distinct way and that
9 * does not exceed LIMIT. These are analogous to taxicab numbers.
10 */
11const GOOD: number[] = ((): number[] => {
12    // Maps each sum value to the number of (a, b) pairs that produce it.
13    const count = new Map<number, number>();
14
15    // Precompute cubes for 0..1000 to avoid recomputation in the loops.
16    const cubes: number[] = Array.from({ length: 1001 }, (_, i) => i * i * i);
17
18    // Enumerate all unordered pairs (a, b) with 1 <= a <= b <= 1000.
19    for (let a = 1; a <= 1000; a++) {
20        for (let b = a; b <= 1000; b++) {
21            const sum = cubes[a] + cubes[b];
22            // Since b only increases, once the sum exceeds LIMIT we can stop.
23            if (sum > LIMIT) break;
24            count.set(sum, (count.get(sum) ?? 0) + 1);
25        }
26    }
27
28    // Keep only the sums that were reached by more than one pair.
29    const result: number[] = [];
30    for (const [sum, occurrences] of count.entries()) {
31        if (occurrences > 1) result.push(sum);
32    }
33
34    // Sort ascending so we can binary-search for query answers later.
35    result.sort((a, b) => a - b);
36    return result;
37})();
38
39/**
40 * Returns all "good" integers that are strictly less than n.
41 *
42 * Uses binary search (sortedLastIndex) to locate the first position whose
43 * value is >= n, then returns the prefix before that index.
44 *
45 * @param n - Exclusive upper bound for the returned good integers.
46 * @returns The sorted list of good integers strictly less than n.
47 */
48function findGoodIntegers(n: number): number[] {
49    // First index at which an element would be >= n.
50    const index = _.sortedLastIndex(GOOD, n);
51    return GOOD.slice(0, index);
52}
53

Time and Space Complexity

Time Complexity: O(m^2 + k log k), where m = 1000 is the enumeration range and k is the number of good integers.

The precomputation phase uses two nested loops over a and b, each ranging up to m = 1000, contributing O(m^2) to build the cnt dictionary. Afterwards, filtering and sorting the good integers takes O(k log k), where k is the number of distinct integers that can be expressed as the sum of two cubes in more than one way. Each call to findGoodIntegers performs a binary search via bisect_right in O(log k) plus an O(idx) slice, but the dominant cost is the one-time precomputation, so the overall time complexity is O(m^2 + k log k).
Space Complexity: O(k), where k is the number of good integers.

The cnt dictionary stores counts for sums of cubes not exceeding LIMIT, and the GOOD list holds the k good integers. The cubes array uses O(m) space, which is dominated by the storage needed for the good integers, so the overall space complexity is O(k).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Upper Bound for the Cube Range (Off-by-One on the Loop Limit)

The most common mistake is choosing a cube range that silently misses valid pairs. Since 1000³ == 10⁹ exactly equals LIMIT, a developer might assume range(1, 1000) is enough and write the loop excluding 1000:

# WRONG: stops at b = 999, so any good integer requiring b = 1000 is lost.
for a in range(1, 1000):
    for b in range(a, 1000):
        ...

Consider a value like 1000³ + 1³ = 1000000001, which exceeds LIMIT and is irrelevant — but pairs such as a³ + 1000³ where the total stays <= LIMIT are impossible only because 1000³ alone already hits the limit. The subtle issue arises near the boundary: if LIMIT were slightly larger (e.g., 2 × 10⁹), then b = 1000, 1001, etc., would legitimately participate, and an under-sized range would drop them.

Solution: Derive the cube bound directly from LIMIT instead of hardcoding it, and make the range inclusive of the maximum needed value:

LIMIT = 10 ** 9
MAX_BASE = round(LIMIT ** (1 / 3)) + 1   # safety margin for float rounding
CUBES = [i ** 3 for i in range(MAX_BASE + 1)]

for a in range(1, MAX_BASE + 1):
    for b in range(a, MAX_BASE + 1):
        cube_sum = CUBES[a] + CUBES[b]
        if cube_sum > LIMIT:
            break
        sum_count[cube_sum] += 1

Computing MAX_BASE from LIMIT (with a +1 cushion to absorb floating-point error in the cube root) guarantees correctness even if LIMIT changes.

Pitfall 2: Double-Counting Pairs by Iterating `b` from `1` Instead of `a`

If the inner loop starts b at 1 rather than at a, every unordered pair gets counted twice — once as (a, b) and once as (b, a):

# WRONG: counts (a, b) and (b, a) separately.
for a in range(1, 1001):
    for b in range(1, 1001):
        ...

This inflates the count of every sum by a factor of 2, which paradoxically still "works" for detecting good integers (since count > 1 remains true), but it also wrongly promotes numbers with a single genuine pair: a value like 2³ + 2³ (one real pair, a == b) is counted once, while 1³ + 2³ (one real pair, a != b) is counted twice — making the non-good 9 = 1³ + 2³ appear "good." This produces false positives.

Solution: Always start the inner loop at b = a so that a <= b holds and each unordered pair is counted exactly once, exactly as the original code does:

for a in range(1, MAX_BASE + 1):
    for b in range(a, MAX_BASE + 1):   # b starts at a
        ...

Pitfall 3: Recomputing `GOOD_INTEGERS` per Query Instead of Once

A natural but costly mistake is to place the entire preprocessing (the double loop and the sort) inside findGoodIntegers. With multiple queries, this repeats the O(M²) work every call:

class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        sum_count = defaultdict(int)          # rebuilt every call!
        for a in range(1, 1001):
            for b in range(a, 1001):
                ...
        good = sorted(...)
        return [x for x in good if x <= n]

For Q queries this becomes O(Q · M²), which can time out.

Solution: Hoist the preprocessing to module level (computed once at import time, as the provided code does), then each query only performs an O(log K) binary search:

# Built once at import time.
GOOD_INTEGERS = sorted(value for value, count in sum_count.items() if count > 1)

class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        idx = bisect_right(GOOD_INTEGERS, n)
        return GOOD_INTEGERS[:idx]

Pitfall 4: Returning a Reference to the Shared List (Mutation Risk)

return GOOD_INTEGERS[:idx] is safe because slicing creates a new list. However, a tempting "optimization" like returning the shared list directly when idx == len(GOOD_INTEGERS) exposes the global to caller mutation:

# RISKY: caller could mutate the shared GOOD_INTEGERS.
if idx == len(GOOD_INTEGERS):
    return GOOD_INTEGERS
return GOOD_INTEGERS[:idx]

If the caller later does result.append(...) or result.sort(...), it corrupts the precomputed data for all subsequent queries.

Solution: Always return a fresh slice (GOOD_INTEGERS[:idx]), which copies the relevant elements and keeps the global immutable from the caller's perspective. The minor copy cost is negligible and the safety guarantee is worth it.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: