3890. Integers With Multiple Sum of Two Cubes
You are given an integer n.
An integer x is considered good if there exist at least two distinct pairs (a, b) such that:
aandbare positive integers.a <= bx = a3 + b3
Return an array containing all good integers less than or equal to n, sorted in ascending order.
Example 1:
Input: n = 4104
Output: [1729,4104]
Explanation:
Among integers less than or equal to 4104, the good integers are:
- 1729:
13 + 123 = 1729and93 + 103 = 1729. - 4104:
23 + 163 = 4104and93 + 153 = 4104.
Thus, the answer is [1729, 4104].
Example 2:
Input: n = 578
Output: []
Explanation:
There are no good integers less than or equal to 578, so the answer is an empty array.
Constraints:
1 <= n <= 109
Hash TableSortingCountingEnumeration
Hints
Hint 1
Iterate over all pairs
(a, b) with a <= b and a3 + b3 <= nHint 2
Use a map to count how many times each value of
a3 + b3 appearsHint 3
A value is good if it can be formed by at least two distinct pairs
Hint 4
Collect all such values and return them in sorted order
Preparing judge…