Write Code vs. Write Poetry: Cube Sum (HashMap)
Question: Please 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.
Idea: Binary search to find the ceiling(power(n,1/3)), then from 0 to the ceiling, we find calculate i^3+j^3, where j is from i+1 to the ceiling and store all the sum in a hashmap<sum, times appeared>. If any sum value shows up more than once, append to the result.
I would suggest not to use math.power(n, 1.0/3), since math.pow(64,1.0/3)=3.99999996.
"Output" is a class I wrote for printing my own tests, the function is just to print a list of integers if the input is not null. If the List<Integer> is null, print an "\n".
Time: O(n^2/3) Space: O(n^2/3)
Question: Please 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.
Idea: Binary search to find the ceiling(power(n,1/3)), then from 0 to the ceiling, we find calculate i^3+j^3, where j is from i+1 to the ceiling and store all the sum in a hashmap<sum, times appeared>. If any sum value shows up more than once, append to the result.
I would suggest not to use math.power(n, 1.0/3), since math.pow(64,1.0/3)=3.99999996.
"Output" is a class I wrote for printing my own tests, the function is just to print a list of integers if the input is not null. If the List<Integer> is null, print an "\n".
Time: O(n^2/3) Space: O(n^2/3)
public List<Integer> getCubeNumbers(int n)
{
List<Integer> result=new ArrayList<Integer>();
int start=0;
int end=cubeRootUp(n);
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=start;i<end;i++)
{
for(int j=i+1;j<=end;j++)
{
int cube=i*i*i+j*j*j;
if(cube<=n&&map.containsKey(cube))
map.put(cube, map.get(cube)+1);
else
map.put(cube, 1);
}
}
for(int key:map.keySet())
{
if(map.get(key)>1)
result.add(key);
}
return result;
}
public int cubeRootUp(int x)
{
long y=(long)x;
long left=0;
long right=x/3;
while(left<=right)
{
long mid=(left+right)/2;
long cube=mid*mid*mid;
if(cube==y)
return (int)mid;
if(cube<x)
left=mid+1;
else
right=mid-1;
}
return (int)left;
} 