CareerCup

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.

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--;
}

}

}

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)

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?

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;
}

def fun(num):
    i = 1
    j = int(num ** (1.0/3))
    count = 0
    while i <= j:
        value = i ** 3 + j ** 3
        if value == num:
            count += 1
            i += 1
            j -= 1
        elif value < num:
            i += 1
        else:
            j -= 1
    
        
    if count == 2:
        return True
    else:
        return False

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 } } }

Find max k: k^3 <= n. h = hash map. h[i^3+j^3]++ for i=0..k, j=0..k, i^3+j^3 < n. Output all keys such that h[key] >= 2. O(n^2/3)

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");
}}}}}}