Problem Statement in English

You’re given an integer n. You have to find all the integers from 1 to n (inclusive) that can be expressed as the sum of cubes of two distinct positive integers in at least two different ways.

Return a list of all such integers sorted in ascending order.

Approach

We just need to brute force all the cubes of integers from 1 to n and store the frequency of the sum of two cubes in a dictionary. Then we can just iterate through the dictionary and add the keys that have a frequency greater than 1 to the result list.

And we’re done!

Solution in Python


class Solution:
    def findGoodIntegers(self, n: int) -> list[int]:
        arr = []

        for i in range(min(3000, n)):
            num = pow(i, 3)

            if num > n:
                break
            arr.append(num)

        hm = defaultdict(int)
        res = []

        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                s = arr[i] + arr[j]

                if s > n:
                    break

                hm[s] += 1

        for k in sorted(hm):
            v = hm[k]
            
            if v > 1:
                res.append(k)

        return res

Complexity

  • Time: $O(n^2)$
    Since we have two nested loops to calculate the sum of two cubes.

  • Space: $O(n)$
    Since we store the cubes of integers in an array and the frequency of sums in a dictionary.

And we are done.