Integers With Multiple Sum of Two Cubes - Solution & Explanation

Problem Overview: Given a bound on integers, identify numbers that can be written as a^3 + b^3 in more than one distinct way. Different pairs (a, b) may produce the same cube sum, and the task is to detect sums that appear multiple times.

Approach 1: Brute Force Pair Enumeration (O(n^2) time, O(1) extra space)

Enumerate every pair (a, b) where 1 ≤ a ≤ b ≤ n. For each pair compute a^3 + b^3 and compare it against previously generated sums by scanning stored results. This approach relies purely on enumeration and repeated comparisons, which makes it simple but inefficient. Time complexity grows to O(n^3) if comparisons require scanning previous results, and even optimized versions still need O(n^2) enumeration. Use this only to demonstrate the mathematical property of cube sums.

Approach 2: Hash Table Counting (O(n^2) time, O(n^2) space)

Enumerate all cube pairs but store the computed sum in a hash table. Each key represents a value of a^3 + b^3, and the value stores how many pairs generate it. When the same sum appears again, increment the counter. After enumeration, every key with count ≥ 2 represents an integer that has multiple cube representations. Hash lookup is O(1), so the algorithm remains dominated by the n^2 pair enumeration. This approach is straightforward and commonly used in interview solutions.

Approach 3: Sort Cube Sums and Count Duplicates (O(n^2 log n) time, O(n^2) space)

Instead of hashing, store all cube sums in an array while enumerating pairs. Sort the array using a standard sorting algorithm. Identical sums become adjacent after sorting, allowing a single pass to count duplicates and detect numbers that appear multiple times. Sorting introduces a log n factor but can be useful when deterministic ordering or offline processing is preferred over hashing.

Approach 4: Ordered Pair Enumeration with Min Heap (O(n^2 log n) time, O(n) space)

A more memory‑efficient technique generates sums in sorted order using a min heap. Start with pairs (a, a) for each a. Push their cube sums into a heap. Each time you pop the smallest sum, push the next pair for that a (i.e., (a, b+1)). This technique resembles merging sorted sequences and is common in enumeration problems. Duplicate sums appear consecutively, making it easy to detect integers with multiple representations. The approach relies on priority queue operations and controlled enumeration rather than storing every pair.

Recommended for interviews: The hash table counting approach is the most practical. It clearly shows you understand pair enumeration and how hash tables eliminate repeated searches. Mentioning brute force first demonstrates reasoning about the search space, while the optimized hash-based solution shows the ability to reduce lookup cost and handle duplicate detection efficiently.