Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
I belive this solution answers a different question. We're not looking for a representation of n , but for all numbers smaller than n, that have the described property.
I believe this solution ansewer a different question. We're not looking for a representation of n, but for all numbers smaller than n that have the described property.
@fatu
I guess the solution does the same thing that you mentioned. A number say less than 'n' can never be greater than 'm' where 'm' is n^1/3. Hence it is enough, to find the numbers less than 'm' . The solution provided first finds 'm' that is n^1/3, it then tries to find the number pairs that obey the given constraint. Let me know if am missing anything in this
@ Fsheriff
Let's say n = 2000, we want all numbers less than 2000 that can be represented as a sum of two different cubes. We know that one of such numbers is 1729.
But applying CalculateCubeSums(n) will only check if n = 2000 can be represented as a sum of two different cubes. So do you intend to do sth like:
for (int i = 0; i < n; ++i) CalculateCubeSums(n) ?
@fatu thanks for the explanation. My bad, I misunderstood the question. I have corrected the code and posted it.
public void calculateCubeSum1(int n) {
int cuberoot = (int) Math.cbrt(n);
for (int i = 1; i <= cuberoot; i++)
for (int j = i; j <= cuberoot; j++)
{
int num = i*i*i+j*j*j;
System.out.println(num);
}
}
Great solution! But I guess you still have an extra step, as I believe your solution is not accomplishing fully what the question asks for, the problem is to print all numbers i < N where i can be expressed by the sum of 2 different cubes in 2 different ways, yours is only checking for pairs that sum up to N. The right way would be to iterate for all the i < N and check for each number i if it has at least 2 different distinct pairs which sum up to N. Please check my solution
public static Set<Integer> sum(int n)
{
Set<Integer> hashset = new HashSet<Integer>();
Set<Integer> ans = new HashSet<Integer>();
int size = (int)Math.cbrt(n);
for (int i = 1; i <= size; i++)
for (int j = i; j <= size; j++)
{
int num = i*i*i+j*j*j;
if (hashset.contains(num))
ans.add(num);
else
hashset.add(num);
}
return ans;
}
O(N^2/3)
Aren't we supposed to also consider sum of cubes of negative numbers? For example, 2^3 + (-1)^3 or 11^3 + (-10)^3 ?
Time Complexity O((n^(1/3))(n^(1/3))(n^(1/3))) = O(n)
Space Complexity: O(1)
void FindCubes( int n )
{
int i,j,k,i3,j3,k3;
int max_cube = pow( (double)n, (double)1/3 );
double cube_root;
int number;
for ( i = 1 ; i < max_cube ; i++ )
{
i3 = i*i*i;
for ( j = i+1 ; j < max_cube ; j++ )
{
j3 = j*j*j;
for ( k = i+1 ; k < max_cube ; k++ )
{
if ( k != j )
{
k3 = k*k*k;
number = i3+j3-k3;
cube_root = ceil( pow( (double)number, (double)1/3 ) );
if ( ( pow( cube_root, 3 ) == number ) && ( cube_root > k ) )
{
printf("%d = %d^3 + %d^3 = %d^3 + %d^3\n", i3+j3 , i,j,k,(int)cube_root );
}
}
}
}
}
}
public static void twoCubesSum(int n) {
if(n < 28) return;
double cubeRoot = Math.cbrt(n);
int fwd = 1;
int bck = (int) cubeRoot;
int count = 2;
while(fwd < bck) {
int cubeFwd = fwd * fwd * fwd;
int cubeBck = bck * bck * bck;
if(cubeFwd + cubeBck == n) {
if(count == 2) {
System.out.println("First pair: " + fwd + ", " + bck);
count--;
} else {
System.out.println("Second pair: " + fwd + ", " + bck);
return;
}
}
if(cubeFwd + cubeBck >= n) {
bck--;
} else {
fwd++;
}
}
}
1729 = 13^3 + 123^3 = 93^3 + 103^3 ??!!
13^3 + 123^3 = 1863064 ; 93^3 + 103^3 = 1897084
Could you please clarify?
I apologize, I had made a typo and added an extra 3 at the end of each number - fixed now (1729 = 1^3 + 12^3 = 9^3 + 10^3).
demonix, can you please clarify?
I'm not sure if I correctly understand the problem, but it's said "represent positive number as the sum of two cubes", therefore one of the cubes may be less than zero. F.e. 98 = (-3)^3 + (5)^3.
def buildHashAndArray(num):
i = 1
array = []
hash = {}
while True:
currCube = i ** 3
if currCube < num:
array.append(currCube)
hash[currCube] = True
else:
return (hash, array)
i += 1
def findCubeSum(num):
hash, array = buildHashAndArray(num)
for curNum in range(1,num,1):
currCombos = []
for i in array:
j = curNum-i
if hash.has_key(j):
if len(currCombos) == 0:
currCombos = [i,j]
else:
if i not in currCombos or j not in currCombos:
print curNum
break
findCubeSum(100000)
Find 0^3...k^3, where k^3 - (k-1)^3 <= n and store in an array. Find sum of all pairs of numbers in this array such that num1 +/- num2 <= n and put these sums as keys in a hashtable and values as their counts. Finally iterate over hashtable to find numbers with counts >= 2. From relation k^3 - (k-1)^3 <= n, we get k is proportional to sqrt(n). Running time O(k^2) / O(n), space complexity O(k^2) / O(n).
Find all values 0^3 to k^3 where k^3 - (k-1)^3 <= n and store in an array. Find sum of all pairs in this array such that num1 +/- num2 <= n. Store all these sums in a hashtable with sums as key and value as count. Finally iterate over hastable to print all sums with counts >= 2.
From relation k^3 - (k-1)^3 <= n, k is proportional to sqrt(n). Running time O(k^2) / O(n), space complexity O(k^2 + k) / O(n).
Find all values 0^3 to k^3 where k^3 - (k-1)^3 <= n and store in an array. Find sum of all pairs in this array such that num1 +/- num2 <= n. Store all these sums in a hashtable with sums as key and value as count. Finally iterate over hastable to print all sums with count >= 2.
From relation k^3 - (k-1)^3 <= n, k is proportional to sqrt(n). Running time O(k^2) / O(n), space complexity O(k^2 + k) / O(n).
Find all values 0^3 to k^3 where k^3 - (k-1)^3 <= n and store in an array. Find sum of all pairs in this array such that num1 +/- num2 <= n. Store all these sums in a hashtable with sums as key and value as count. Finally iterate over hastable to print all sums with count >= 2.
From relation k^3 - (k-1)^3 <= n, k is proportional to sqrt(n). Running time O(k^2) / O(n), space complexity O(k^2 + k) / O(n).
Find all values 0^3 to k^3 where k^3 - (k-1)^3 <= n and store in an array. Find sum of all pairs in this array such that num1 +/- num2 <= n. Store all these sums in a hashtable with sums as key and value as count. Finally iterate over hastable to print all sums with count >= 2.
From relation k^3 - (k-1)^3 <= n, k is proportional to sqrt(n). Running time O(k^2) / O(n), space complexity O(k^2 + k) / O(n).
O(1) space, O(n^1/3) time
import math
class CubeSum():
def find_cube_sum(self, n):
lst = []
c = int(math.ceil((n/2.0)**(1/3.0)))
if c**3 > n/2.0:
c -= 1
for i in range(c+1):
diff = n - i**3
j = int(math.ceil(diff**(1/3.0)))
if j**3 == diff and min(i,j)!=0:
lst.append((i, j))
if len(lst)==2:
for item in lst:
i,j = item
print '{2} = {0}^3 + {1}^3'.format(i, j, n)
if __name__ == '__main__':
cs = CubeSum()
for i in range(1000000):
cs.find_cube_sum(i)
public static void main(String[] args) {
System.out.println(cube(20000));
}
public static String cube(int n) {
String str = "";
double max = Math.cbrt(n);
int[] found = new int[n];
for (int i = 1; i < max; i++) {
for (int j = i; j < max; j++) {
int sum = (int)(Math.pow(i, 3) + Math.pow(j, 3));
if (sum < n) {
if (found[sum] == 0) {
found[sum]++;
} else if (found[sum] == 1) {
str += sum + "\n";
found[sum]++;
}
}
}
}
return str;
}
O(n^(2/3))
The approach goes like this
Step 1 : Find the cube root of the given 'n', lets call it as 'cubeRoot'
Step2 : Construct an array of size 'cubeRoot' with the (index +1) cubed as the value in the array[index]
For example: For the given 1029, 'cubeRoot' is 12 , a[0]=1, a[1] =8 ... a[11] = 1728
Step3: From here on, it is a famous problem of "Find 2 numbers in a sorted array equal to a given sum "
I have provided the below in java.
public void calculateCubeSum(int n) {
int cuberoot = (int) Math.cbrt(n);
int[] a = new int[cuberoot];
// construct array
for (int i = 0; i < cuberoot; i++) {
a[i] = (i +1) * (i+1) * (i+1);
}
// use forward and backward technique
int fwd = 0;
int bck = cuberoot - 1;
while (fwd < bck) {
if (a[fwd] + a[bck] < n)
fwd++;
else if (a[fwd] + a[bck] > n)
bck--;
else {
System.out
.println(Math.cbrt(a[fwd]) + ", " + Math.cbrt(a[bck]));
fwd++;
bck--;
}
}
}
The approach goes like this
Step 1 : Find the cube root of the given 'n', lets call it as 'cubeRoot'
Step2 : Construct an array of size 'cubeRoot' with the (index +1) cubed as the value in the array[index]
For example: For the given 1029, 'cubeRoot' is 12 , a[0]=1, a[1] =8 ... a[11] = 1728
Step3: From here on, it is a famous problem of "Find 2 numbers in a sorted array equal to a given sum "
I have provided the below in java.
public void calculateCubeSum(int n) {
int cuberoot = (int) Math.cbrt(n);
int[] a = new int[cuberoot];
// construct array
for (int i = 0; i < cuberoot; i++) {
a[i] = (i +1) * (i+1) * (i+1);
}
// use forward and backward technique
int fwd = 0;
int bck = cuberoot - 1;
while (fwd < bck) {
if (a[fwd] + a[bck] < n)
fwd++;
else if (a[fwd] + a[bck] > n)
bck--;
else {
System.out
.println(Math.cbrt(a[fwd]) + ", " + Math.cbrt(a[bck]));
fwd++;
bck--;
}
}
}
Solved problem with C#
public void calcSumCube(double n)
{
double max = Math.Pow(n, 1d / 3d);
double min = 0;
List<double> numbers = new List<double>();
int sum;
for (double i = max; i > 0; i--)
{
sum = (int)(Math.Pow(i, 3) + Math.Pow(i - 1, 3));
if (sum < n || numbers.Count > 2)
break;
else
{
for (double j = min; j < i; j++)
{
sum = (int)(Math.Pow(i, 3) + Math.Pow(j, 3));
if (sum == n)
{
min = j + 1;
numbers.Add(i);
numbers.Add(j);
}
if (numbers.Count > 2 || sum > n)
break;
}
}
}
if (numbers.Count > 2)
foreach (int number in numbers)
Console.WriteLine(number);
}
Worked the problem with c#
public void CalcSumCube(double n)
{
double max = Math.Pow(n, 1d / 3d);
double min = 0;
List<double> numbers = new List<double>();
int sum;
for (double i = max; i > 0; i--)
{
sum = (int)(Math.Pow(i, 3) + Math.Pow(i - 1, 3));
if (sum < n || numbers.Count > 2)
break;
else
{
for (double j = min; j < i; j++)
{
sum = (int)(Math.Pow(i, 3) + Math.Pow(j, 3));
if (sum == n)
{
min = j + 1;
numbers.Add(i);
numbers.Add(j);
}
if (numbers.Count > 2 || sum > n)
break;
}
}
}
if (numbers.Count > 2)
foreach (int number in numbers)
Console.WriteLine(number);
}
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
void main(int argc, char **argv)
{
if (argc != 2)
{
printf("Syntax: <exe> <number>\n");
exit(1);
}
int givenNum = atoi(argv[1]);
int cbroot = (int) cbrt((double)givenNum);
int * table = malloc(sizeof(int)* (cbroot+1));
int * table2 = malloc(sizeof(int) * (givenNum+1));
memset(table2,0, (givenNum+1) * sizeof(int));
int i =1;
while(i <=cbroot)
{
table[i] = i * i * i;
i++;
}
i =1;
while(i <= cbroot)
{
int j =1;
while(j <= cbroot)
{
int sum = table[i] + table [j];
if (sum <= givenNum )
{
// printf("%d cube + %d cube = %d\n", i,j, sum);
table2[sum] = table2[sum] + 1;
if (table2[sum] >= 4)
{
printf("table2[%d] -> %d\n",sum,table2[sum]);
}
}
j++;
}
i++;
}
free(table);
table = NULL;
free(table2);
table2 = NULL;
}
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
void main(int argc, char **argv)
{
if (argc != 2)
{
printf("Syntax: <exe> <number>\n");
exit(1);
}
int givenNum = atoi(argv[1]);
int cbroot = (int) cbrt((double)givenNum);
int * table = malloc(sizeof(int)* (cbroot+1));
int * table2 = malloc(sizeof(int) * (givenNum+1));
memset(table2,0, (givenNum+1) * sizeof(int));
int i =1;
while(i <=cbroot)
{
table[i] = i * i * i;
i++;
}
i =1;
while(i <= cbroot)
{
int j =1;
while(j <= cbroot)
{
int sum = table[i] + table [j];
if (sum <= givenNum )
{
// printf("%d cube + %d cube = %d\n", i,j, sum);
table2[sum] = table2[sum] + 1;
if (table2[sum] >= 4)
{
printf("table2[%d] -> %d\n",sum,table2[sum]);
}
}
j++;
}
i++;
}
free(table);
table = NULL;
free(table2);
table2 = NULL;
}
Time Complexity : O(n^2/3)
Space Complexity: O(n)
import math
n = input("Enter the number")
match = []
e = 0.00000001
for x in range(1,n):
# print "X : "+str(x)
cuberoot = int(x ** (1 / 3.0))
# print "CubeRoot: "+str(cuberoot)
matches = []
for y in range(1,cuberoot):
remainder = x - y**3
# print "Remainder: "+str(remainder)
remainder_root = remainder ** (1 / 3.0)
# print "Remainder Root: "+str(remainder_root)
_max = int(round(remainder_root))+e
_min = int(round(remainder_root))-e
print _max,_min, _max > remainder_root> _min
if _max > remainder_root> _min :
matches.append((x,y,int(round(remainder_root))))
print matches
if len(matches)==2:
match.append((x,matches))
print match
import math
n = input("Enter the number")
match = []
e = 0.00000001
for x in range(1,n):
# print "X : "+str(x)
cuberoot = int(x ** (1 / 3.0))
# print "CubeRoot: "+str(cuberoot)
matches = []
for y in range(1,cuberoot):
remainder = x - y**3
# print "Remainder: "+str(remainder)
remainder_root = remainder ** (1 / 3.0)
# print "Remainder Root: "+str(remainder_root)
_max = int(round(remainder_root))+e
_min = int(round(remainder_root))-e
print _max,_min, _max > remainder_root> _min
if _max > remainder_root> _min :
matches.append((x,y,int(round(remainder_root))))
print matches
if len(matches)==2:
match.append((x,matches))
print match
import math
n = input("Enter the number")
match = []
e = 0.00000001
for x in range(1,n):
# print "X : "+str(x)
cuberoot = int(x ** (1 / 3.0))
# print "CubeRoot: "+str(cuberoot)
matches = []
for y in range(1,cuberoot):
remainder = x - y**3
# print "Remainder: "+str(remainder)
remainder_root = remainder ** (1 / 3.0)
# print "Remainder Root: "+str(remainder_root)
_max = int(round(remainder_root))+e
_min = int(round(remainder_root))-e
print _max,_min, _max > remainder_root> _min
if _max > remainder_root> _min :
matches.append((x,y,int(round(remainder_root))))
print matches
if len(matches)==2:
match.append((x,matches))
print match
public class CubicNumbers {
public static void main(String[] args){
long n = 50000000;
long x = (long) Math.pow(n, 1.0/3) + 1;
Map<Long, List<Pair<Long, Long>>> map = new HashMap<Long, List<Pair<Long, Long>>>();
for (long i=1; i <= x; i++){
long y = (long) Math.pow(n - Math.pow(i, 3), 1.0/3) + 1;
for (long j=1 ; j <= y; j++){
long cube = (long) (Math.pow(i, 3) + Math.pow(j, 3));
if (cube > n){
continue;
}
long min = Math.min(i, j);
long max = Math.max(i, j);
Pair<Long, Long> pair = new Pair<Long, Long>(min, max);
if (!map.containsKey(cube)){
map.put(cube, new ArrayList<Pair<Long, Long>>());
}
boolean present = false;
for (Pair<Long, Long> p : map.get(cube)){
// since we always put min as key and max as val
// we can compare key to key and val to val
if (p.getKey().equals(pair.getKey()) &&
p.getValue().equals(pair.getValue())){
present = true;
}
}
if (!present){
map.get(cube).add(pair);
}
}
}
for (Long cube : map.keySet()){
List<Pair<Long, Long>> pairs = map.get(cube);
// do not necessarily want to ignore greater than two though
if (pairs.size() == 2){
System.out.println(cube);
}
}
}
}
public class CubicNumbers {
public static void main(String[] args){
long n = 50000000;
long x = (long) Math.pow(n, 1.0/3) + 1;
Map<Long, List<Pair<Long, Long>>> map = new HashMap<Long, List<Pair<Long, Long>>>();
for (long i=1; i <= x; i++){
long y = (long) Math.pow(n - Math.pow(i, 3), 1.0/3) + 1;
for (long j=1 ; j <= y; j++){
long cube = (long) (Math.pow(i, 3) + Math.pow(j, 3));
if (cube > n){
continue;
}
long min = Math.min(i, j);
long max = Math.max(i, j);
Pair<Long, Long> pair = new Pair<Long, Long>(min, max);
if (!map.containsKey(cube)){
map.put(cube, new ArrayList<Pair<Long, Long>>());
}
boolean present = false;
for (Pair<Long, Long> p : map.get(cube)){
// since we always put min as key and max as val
// we can compare key to key and val to val
if (p.getKey().equals(pair.getKey()) &&
p.getValue().equals(pair.getValue())){
present = true;
}
}
if (!present){
map.get(cube).add(pair);
}
}
}
for (Long cube : map.keySet()){
List<Pair<Long, Long>> pairs = map.get(cube);
// do not necessarily want to ignore greater than two though
if (pairs.size() == 2){
System.out.println(cube);
}
}
}
}
public void FindCubeCombinations(int Number)
{
for (int i = 1; i < Number; i++)
{
int Remain = Number - i * i * i;
if (Remain < 0) break;
for (int j = i + 1; j < Remain; j++)
{
if (Remain - j * j * j == 0)
{
Console.WriteLine(string.Format("{0} - {1}", i, j));
break;
}
else if (Remain - j * j * j < 0)
break;
}
}
}
public void FindCubeCombinations(int Number)
{
for (int i = 1; i < Number; i++)
{
int Remain = Number - i * i * i;
if (Remain < 0) break;
for (int j = i + 1; j < Remain; j++)
{
if (Remain - j * j * j == 0)
{
Console.WriteLine(string.Format("{0} - {1}", i, j));
break;
}
else if (Remain - j * j * j < 0)
break;
}
}
}
public void FindCubeCombinations(int Number)
{
for (int i = 1; i < Number; i++)
{
int Remain = Number - i * i * i;
if (Remain < 0) break;
for (int j = i + 1; j < Remain; j++)
{
if (Remain - j * j * j == 0)
{
Console.WriteLine(string.Format("{0} - {1}", i, j));
break;
}
else if (Remain - j * j * j < 0)
break;
}
}
}
public static void twoCubesSum(int n) {
if(n < 28) return;
double cubeRoot = Math.cbrt(n);
int fwd = 1;
int bck = (int) cubeRoot;
int count = 2;
while(fwd < bck) {
int cubeFwd = fwd * fwd * fwd;
int cubeBck = bck * bck * bck;
if(cubeFwd + cubeBck == n) {
if(count == 2) {
System.out.println("First pair: " + fwd + ", " + bck);
count--;
} else {
System.out.println("Second pair: " + fwd + ", " + bck);
return;
}
}
if(cubeFwd + cubeBck >= n) {
bck--;
} else {
fwd++;
}
}
}
public static void twoCubesSum(int n) {
if(n < 28) return;
double cubeRoot = Math.cbrt(n);
int fwd = 1;
int bck = (int) cubeRoot;
int count = 2;
while(fwd < bck) {
int cubeFwd = fwd * fwd * fwd;
int cubeBck = bck * bck * bck;
if(cubeFwd + cubeBck == n) {
if(count == 2) {
System.out.println("First pair: " + fwd + ", " + bck);
count--;
} else {
System.out.println("Second pair: " + fwd + ", " + bck);
return;
}
}
if(cubeFwd + cubeBck >= n) {
bck--;
} else {
fwd++;
}
}
}
maxnum = int(math.pow(10000, 1.0/3))
cubes = [n * n * n for n in range(1, maxnum)]
print(cubes)
pairs = [(a, b) for a in cubes for b in cubes if a < b]
print(pairs)
ret = {}
for pair in pairs:
num = pair[0] + pair[1]
ret[num] = ret.get(num, 0) + 1
sums_of_cubes = list(key for key in ret if ret[key]>1)
print(sums_of_cubes)
print(list(pair for pair in pairs if pair[0]+pair[1] in sums_of_cubes))
Using the two pointer idea when getting the elements, time complexity is O(N), space is O(N), too.
class Solution:
def findCube(self,N):
elements = []
for i in range(1,N):
if math.pow(i,3)<N:
elements.append(math.pow(i,3))
else:
break
output = []
left = 0
right = len(elements)-1
while(left<right):
curr = int(elements[left] + elements[right])
if curr== N:
output.append([int(elements[left]),int(elements[right])])
left +=1
right -=1
elif curr<N:
left +=1
else:
right -=1
return output
// TIME: O(n + n^(2/3))
// SPACE: O(n^(2/3))
#include <vector>
#include <cmath>
#include <map>
#include <iostream>
void print_combos(int n) {
std::vector<int> cubes;
int cuberoot_max = int(pow(n, 1.0 / 3.0)) + 1;
for (int i = 1; i <= cuberoot_max; ++i) {
cubes.push_back(i*i*i);
}
int cubes_sz = int(cubes.size()); // == cuberoot_max
std::map<int, int> nc;
for (int i = 0; i < cubes_sz; ++i) {
for (int j = i; j < cubes_sz; ++j) {
nc[cubes[i] + cubes[j]] += 1;
}
}
for (int i = 1; i <= n; ++i) {
if (nc.count(i) && nc[i] >= 2) {
std::cout << i << std::endl;
}
}
}
int main() {
int N = 15000;
print_combos(N);
}
1. runtime is o(n)
2. we can save a bit by calculating the max possible value that
can be found which is the cube root of the number
3. Can be easily adjusted to store the findings and only print them
if there is more then one pair.
void FindPairs(int num) {
int max = Math.pow(num, 1/3);
int[] buff = new int[max];
for(int index=0; indedx<=max; index++) {
buff[index] = Math.pow(index, 3);
}
int start = 0;
int end = buff.length-1;
while(start < end) {
int sum = buff[start] + buff[end]
if(sum == num)
System.out.println(buff[start] + " , " + buff[end]);
else(sum < num)
start++;
else
end--;
}
}
static boolean hasTwoCubeReps(int n) {
int lo = 0;
int hi = (int)Math.cbrt(n);
int cnt = 0;
while(lo <= hi) {
int scbs = lo*lo*lo + hi*hi*hi;
if (scbs == n) {
lo++; hi--;
cnt++;
} else if (scbs < n) {
lo++;
} else {
hi--;
}
}
return cnt >= 2;
}
static void printAllSmallerWithTwoCubeReps(int n) {
for (int i = 0; i < n; ++i)
if (hasTwoCubeReps(i)) System.out.println(i);
}
the problem is to print all numbers i < N where i can be expressed by the sum of 2 different cubes in 2 different ways, The right way would be to iterate for all the i < N and check for each number i if it has at least 2 different distinct cubic pairs which sum up to N.
The algorithm below follows this aproach:
package tempProject2;
public class Solution {
public static void main(String[] args) {
System.out.println(printAllNumbersSmallerThanNCubeSum(1730, 2));
}
public static final int printAllNumbersSmallerThanNCubeSum(int n, int k) {
if (n <= 1 || k <= 0) {
return 0;
}
Double cb = new Double(n);
cb = Math.cbrt(cb);
int cbroot = cb.intValue();
int count = 0;
int[] cubes = new int[cbroot];
for (int i = 0; i < cubes.length; i++) {
cubes[i] = (i + 1) * (i + 1) * (i + 1);
}
int lowerBound = cubes.length > 1 ? 1 + cubes[1] : 1;
for (int i = 1; i < n; i++) {
if (i >= lowerBound) {
if (countPossiblePairSums(i, cubes) >= k) {
count++;
}
}
}
return count;
}
public static int countPossiblePairSums(int sum, int[] cubes) {
int count = 0;
int i = 0;
int j = cubes.length - 1;
while (i < j) {
if (cubes[i] + cubes[j] == sum) {
count++;
i++;
j--;
} else if (cubes[i] + cubes[j] > sum) {
j--;
} else if (cubes[i] + cubes[j] < sum) {
i++;
}
}
return count;
}
}
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.
Follow more details on: cpluspluslearning-petert.blogspot.co.uk/2015/04/data-structure-and-algorithm-find-all_30.html
Will operate in O(n^(4/3)) time with O(n^(1/3)) memory
public static ArrayList<Integer> getAllPaired2Sums(int n){
//compute all cube roots up to the cube root of n
HashSet<Integer> cubes = new HashSet<Integer>();
int index = 0;
int cube = 0;
while(cube < n){
index++;
cube = index * index * index;
cubes.add(cube);
}
ArrayList<Integer> results = new ArrayList<Integer>();
//compute pairs
outer:for(index = 9; index <= n; index++){
boolean hasPair = false;
for(int i = 1; (cube = i*i*i) < index; i++){
if(cubes.contains(index - cube)){
if(hasPair){
results.add(index);
continue outer;
}
else{
hasPair = true;
}
}
}
}
return results;
}
import java.util.*;
public class Main {
private static Map<Integer, Pair[]> cubeSum(int n) {
Map<Integer, Pair[]> result = new HashMap<>();
int nCube = (int) Math.cbrt(n);
int[] relevant = new int[nCube];
relevant[nCube - 1] = n;
for(int i = 1; i < nCube; ++i) {
relevant[i - 1] = (int) Math.pow(i, 3);
}
for(int i = 1; i < n; ++i) {
cubeSum(i, result, relevant);
}
return result;
}
private static void cubeSum(int n, Map<Integer, Pair[]> result, int[] relevant) {
int count = 0;
int left = 0, right = 0;
while(relevant[right + 1] < n) {
++right;
}
Pair[] sums = new Pair[2];
while(left < right) {
if(relevant[left] + relevant[right] < n) {
++left;
} else if(relevant[left] + relevant[right] > n) {
--right;
} else {
sums[count] = new Pair(relevant[left], relevant[right]);
++count;
if(count == 2) {
result.put(n, sums);
return;
}
++left;
--right;
}
}
}
private static void printResult(Map<Integer, Pair[]> result) {
for(Map.Entry<Integer, Pair[]> entry: result.entrySet()) {
int key = entry.getKey();
Pair[] values = entry.getValue();
System.out.println(key + " may be represented as " + values[0] + " and " + values[1]);
}
}
public static void main(String... args) {
Map<Integer, Pair[]> result = cubeSum(20000);
printResult(result);
}
}
public class Pair {
int a;
int b;
int aCube;
int bCube;
public Pair(int aNew, int bNew) {
if(aNew >= bNew) {
int temp = aNew;
aNew = bNew;
bNew = temp;
}
this.a = (int) Math.cbrt(aNew);
this.b = (int) Math.cbrt(bNew);
this.aCube = aNew;
this.bCube = bNew;
}
@Override
public String toString() {
return a + "^3" + " + " + b + "^3 (" + aCube + " + " + bCube + ")";
}
}
Unlike most of the other answers, this code solves the defined problem. The complexity is O( n^(4/3) ).
public List<Tuple<int, int, int, int>> FindCubics(int n)
{
List<int> cubics = new List<int>();
int i = 0;
int m = 0;
while (m < n)
{
cubics.Add(m);
i++;
m = i * i * i;
}
var result = new List<Tuple<int, int, int, int>>();
for (i = 0; i < cubics.Count; i++)
{
for (int j = cubics.Count - 1; j > i; j--)
{
int target = cubics[i] + cubics[j];
int start = i + 1;
int end = j - 1;
while (start < end)
{
int value = cubics[start] + cubics[end];
if (value == target)
{
result.Add(Tuple.Create(cubics[i], cubics[j], cubics[start], cubics[end]));
break;
}
else if (value < target)
start++;
else
end--;
}
}
}
return result;
}
public void ThreePowerSum(){
int number = 13;
List<PowerThree> list = new ArrayList();
for (int i = 1; i < number-1; i++) {
for (int j = i+1; j < number; j++) {
double result = Math.pow(Double.valueOf(i+""), 3) + Math.pow(Double.valueOf(String.valueOf(j)), 3);
PowerThree powerThree = new PowerThree(result, i, j);
boolean hasPair = false;
for (int k = 0; k < list.size(); k++) {
if(list.get(k).result == powerThree.result){
System.out.println("match! " + powerThree.result + " with values:\n" + powerThree.firstCube + " and " + powerThree.secondCube + "\n" +
list.get(k).firstCube + " and " + list.get(k).secondCube);
hasPair = true;
}
}
if(!hasPair){
list.add(powerThree);
}
}
}
}
public class PowerThree{
double result;
int firstCube;
int secondCube;
public PowerThree(double result, int firstCube, int secondCube) {
this.result = result;
this.firstCube = firstCube;
this.secondCube = secondCube;
}
shortest answer is in kdb :) , the below finds all such occurances.
t:delete from ([] a:1 2 3;b:4 5 6;s:1 2 3)
f1:{ { `t upsert ([] a:x;b:y;s:(x*x*x) + (y*y*y)); }[;y] each x }
f2:{ raze f1[;y] each x }[L1;L2]
p:select a, b by s from t
p:update ca:{count each x}[a] , cb:{count each x}[b] from p
select from p where ca>2
This will do in kdb :) short and sweet. the complexity is O(N^2) cant be reduced below that :)
{ { { t:delete from ([] a:1 2 3;b:4 5 6;s:1 2 3)
f1:{ { `t upsert ([] a:x;b:y;s:(x*x*x) + (y*y*y)); }[;y] each x }
f2:{ raze f1[;y] each x }[L1;L2]
p:select a, b by s from t
p:update ca:{count each x}[a] , cb:{count each x}[b] from p
select from p where ca>2 } } }
I'm pretty sure there is a better way but this is what I got. I suspect it can be done in constant time using some relation with cubes. This is n^2
public static void main(String [] args){
printNums(sumOfCubes(1000));
}
static HashSet<Integer> sumOfCubes(int n){
HashSet<Integer> nums = new HashSet<Integer>();
int size = (int) Math.pow((double) n, (double) 1/3);
int first;
int second;
int total;
for(int x = 0; x <= size; x++){
for(int i = 0; i <= size; i++){
first = (int) Math.pow(x, 3);
second = (int) Math.pow(i, 3);
//check value
total = first + second;
if(total < n) nums.add(total);
}
}
return nums;
}
static void printNums(HashSet<Integer> nums){
for(Integer ints : nums){
System.out.println(ints);
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Problem3 {
public static void main(String args[]){
int number = 1729;
int base = (int) Math.cbrt(number);
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i <= base; i++){
for(int j = 0; j <= base; j++){
if((Math.pow(i, 3)+Math.pow(j, 3)) == number){
if(!map.containsKey(i) && !map.containsKey(j)){
map.put(i,1);
map.put(j, 1);
System.out.println(i+"^3 + "+j+"^3");
}}}}}}
The approach goes like this
Step 1 : Find the cube root of the given 'n', lets call it as 'cubeRoot'
Step2 : Construct an array of size 'cubeRoot' with the (index +1) cubed as the value in the array[index]
For example: For the given 1029, 'cubeRoot' is 12 , a[0]=1, a[1] =8 ... a[11] = 1728
Step3: From here on, it is a famous problem of "Find 2 numbers in a sorted array equal to a given sum "
I have provided the code below in java.
- fsheriff February 19, 2015