Data Structure and Algorithm - Find All Values as the Sum of Two Cubes in Two Different Ways Under N (Google Interview Question)

1. Problem Description

This is a Google interview question for software engineer inters from careercup. Here is the original thread, 

"

Write a function that would print all positive numbers smaller than n that can be expressed as the sum of two cubes in two different ways. Bonus: calculate the complexity of that function. 

For example, 1729 is one such number because 1729 = 1^3 + 12^3 = 9^3 + 10^3.

"

2. Analysis

The simplest way is to use brutal force to iterate from 1 to N and check if this value is the sum of two cubes in two different combinations. Iterating each value takes a linear way. For each value i, it takes (i^1/3) to check if it is the sum of two cubes and has only two combinations. All together the computation complexity is more than O(N) and less than O(N^(4/3)).

The brutal force approach is worse than linear computation, therefore it is not good enough. As some of contributors points out, the correct way is to find out all the cubes under N and then see if value i can be sum of two and has only two combinations.

Rather than take the top-down approach. Here I would like to take bottom-up approach. After find out all the cubes under N, rather than check if value i can be sum of two and has only two combinations, I would compute all the possible sums of two cubes and their frequency. And those sums that are no more than N and the frequency equal to 2 are what I am after.

Given N and all cubes no greater than N as {X1, X2, ..., Xm}, where m = the integer no greater than (N^1/3). Then computer all possible sums, SUM = Xi + Xj, where i is not equal to j and both range from 1 to M. In maximum it would have M*(M-1)/2 possible SUMs. And those are no greater than N and appear exactly twice meet the requirement.

3. Solution

Pseudo-code

    - 1. Find out all cubes under N as {X1, X2, ..., Xm}

    - 2. Compute all possible SUM = Xi+Xj and increment its frequency

    - 3. Filter out SUM no greater than N and its frequency equal to 2

Counting the frequency associated with the SUM could use the hash map by SUM as the key and the frequency as the value. It takes constant time to search and linear time to filter out those meet the requirement.

Complexity

    - M equal to the integer no greater than N^(1/3)

    - In maximum has M*(M-1)/2 possible SUM

Therefore the computation complexity is O(N^(2/3)) and space complexity is O(N^(1/3)+N^(2/3)). Both are better than linear complexity.