LeetCode 3890 - Integers With Multiple Sum of Two Cubes

The problem asks us to find all integers x less than or equal to a given integer n such that x can be expressed as the sum of cubes of two positive integers in at least two distinct ways.

leetcodemediumhash-tablesortingcountingenumeration

LeetCode Problem 3890

Difficulty: 🟡 Medium
Topics: Hash Table, Sorting, Counting, Enumeration

Solution

Problem Understanding

The problem asks us to find all integers x less than or equal to a given integer n such that x can be expressed as the sum of cubes of two positive integers in at least two distinct ways. A “distinct way” means that the pairs (a, b) used to form x are different, where a and b are positive integers with a <= b.

In other words, we are searching for numbers that can be written as a^3 + b^3 = x for at least two distinct pairs (a, b). These numbers are sometimes known in number theory as taxicab numbers. The input n can be as large as 10^9, which rules out naive approaches that enumerate all possible sums blindly. The expected output is a sorted list of these "good integers".

Important edge cases include small values of n (e.g., less than the smallest taxicab number 1729), cases where n is exactly a taxicab number, and situations where multiple numbers satisfy the condition.

Approaches

Brute Force Approach

A brute-force approach would be to iterate over all pairs (a, b) such that a^3 + b^3 <= n, storing each sum in a map or dictionary to count how many distinct pairs produce that sum. After processing all pairs, we would collect the sums that appear more than once. This approach works because it directly follows the definition, but it is inefficient: if n is around 10^9, a and b can be up to roughly 1000 (1000^3 = 10^9), which makes the nested loop O(n^(2/3)). For the worst case, this results in roughly a million iterations-manageable but not optimal for repeated queries.

Optimal Approach

The key insight is that we only need sums of cubes of positive integers up to cbrt(n). Using a two-pointer approach over the sorted list of cubes can generate sums in ascending order efficiently. Alternatively, iterating a from 1 to cbrt(n) and for each a, iterating b from a upwards until a^3 + b^3 > n ensures that we do not compute unnecessary sums. We then use a hash map to track counts of sums. Any sum appearing more than once is a "good integer." This is far more efficient because it avoids storing all pairings in a list, reduces redundant calculations, and scales well with n up to 10^9.

Approach Time Complexity Space Complexity Notes
Brute Force O((n^(1/3))^2) = O(n^(2/3)) O(n^(2/3)) Iterates all pairs (a, b) without pruning
Optimal O(n^(2/3)) O(n^(2/3)) Uses hash map to count sums, prunes b loop early

Algorithm Walkthrough

  1. Compute the integer cube root of n to determine the maximum possible value for a and b. Let this be max_val.
  2. Initialize an empty hash map sum_count to store the counts of sums of two cubes.
  3. Loop a from 1 to max_val.
  4. For each a, loop b from a to max_val. Compute sum_cube = a^3 + b^3.
  5. If sum_cube exceeds n, break the inner loop, because further increasing b will only increase the sum.
  6. Otherwise, increment sum_count[sum_cube] by 1.
  7. After completing all loops, filter the keys in sum_count that have a count greater than 1. These are the "good integers."
  8. Sort the resulting list in ascending order and return it.

Why it works: The invariant is that sum_count[x] correctly records the number of distinct (a, b) pairs that sum to x. By only including sums that appear more than once, we ensure we capture exactly those integers with multiple representations as sums of two cubes.

Python Solution

class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        from collections import defaultdict
        import math
        
        max_val = int(n ** (1/3)) + 1
        sum_count = defaultdict(int)
        
        for a in range(1, max_val + 1):
            a_cubed = a ** 3
            if a_cubed > n:
                break
            for b in range(a, max_val + 1):
                sum_cube = a_cubed + b ** 3
                if sum_cube > n:
                    break
                sum_count[sum_cube] += 1
        
        result = [num for num, count in sum_count.items() if count > 1]
        result.sort()
        return result

The code first computes the largest integer whose cube is ≤ n. Then it iterates over all valid (a, b) pairs using nested loops, but the inner loop stops as soon as the sum exceeds n. Using defaultdict, we count occurrences of each sum. Finally, sums appearing more than once are collected and sorted.

Go Solution

func findGoodIntegers(n int) []int {
    maxVal := 0
    for i := 1; i*i*i <= n; i++ {
        maxVal = i
    }

    sumCount := make(map[int]int)
    for a := 1; a <= maxVal; a++ {
        aCubed := a * a * a
        if aCubed > n {
            break
        }
        for b := a; b <= maxVal; b++ {
            sumCube := aCubed + b*b*b
            if sumCube > n {
                break
            }
            sumCount[sumCube]++
        }
    }

    result := []int{}
    for num, count := range sumCount {
        if count > 1 {
            result = append(result, num)
        }
    }

    // Sort the result
    for i := 0; i < len(result)-1; i++ {
        for j := i + 1; j < len(result); j++ {
            if result[i] > result[j] {
                result[i], result[j] = result[j], result[i]
            }
        }
    }
    return result
}

The Go version mirrors the Python logic. Maps are used for counting. Since Go does not have a built-in sorting for slices of integers without importing sort, a simple bubble sort is applied here for clarity. Using make(map[int]int) ensures we can count sums efficiently.

Worked Examples

Example 1: n = 4104

  1. Compute max_val = int(cbrt(4104)) + 1 = 16.
  2. Iterate a from 1 to 16 and b from a to 16.
  3. Track sums:
a b a³+b³ sum_count
1 ... ... ...
1 16 1+4096=4097 1
9 10 729+1000=1729 1
1 ... ... ...
9 10 729+1000=1729 2

Finally, sums with count > 1 are [1729, 4104].

Example 2: n = 578

  1. max_val = int(cbrt(578)) + 1 = 9
  2. All pairs (a, b) produce sums less than 578.
  3. No sum occurs more than once. Result is [].

Complexity Analysis

Measure Complexity Explanation
Time O(n^(2/3)) The outer loop runs up to cbrt(n), inner loop also up to cbrt(n). Hash map insertions are O(1).
Space O(n^(2/3)) Hash map stores sums generated from all (a, b) pairs, which is bounded by O(n^(2/3)).

Even though worst-case time is O(n^(2/3)), the pruning in the inner loop ensures we do not perform unnecessary computations, making it efficient for n ≤ 10^9.

Test Cases

s = Solution()

# Provided examples
assert s.findGoodIntegers(4104) == [1729, 4104]  # multiple representations
assert s.findGoodIntegers(578) == []  # no good integers

# Edge cases
assert s.findGoodIntegers(1) == []  # n smaller than smallest good integer
assert s.findGoodIntegers(1729) == [1729]  # exactly first good integer
assert s.findGoodIntegers(5000) == [1729, 4104]  # multiple good integers

# Larger n
assert s.findGoodIntegers(20000) == [1729, 4104, 13832]  # next known taxicab numbers
Test Why
n = 4104 Checks normal case with multiple good integers
n = 578 Checks