CODEWITHSUNDEEP
mathcubes
Srivatsa Sinha
Srivatsa Sinha

Reputation: 313

Efficient program to check whether a number can be expressed as sum of two cubes

I am trying to write a program to check whether a number N can be expressed as the sum of two cubes i.e. N = a^3 + b^3

This is my code with complexity O(n):

#include <iostream>
#include<math.h>
#define ll unsigned long long
using namespace std;

int main()
{
 ios_base::sync_with_stdio(false);
 bool flag=false;
 ll t,N;
 cin>>t;
 while(t--)
 {
     cin>>N;
     flag=false;
     for(int i=1; i<=(ll)cbrtl(N/2); i++)
     {
       if(!(cbrtl(N-i*i*i)-(ll)cbrtl(N-i*i*i))) {flag=true; break;}
     }
     if(flag) cout<<"Yes\n"; else cout<<"No\n";
 }
 return 0;
}

As the time limit for code is 2s, This program is giving TLE? can anyone suggest a faster approch

Upvotes: 3

Views: 5808

Answers (3)

SiminSimin
SiminSimin

Reputation: 372

Observe that a^3+b^3=(a+b)(a^2+b^2-ab)

Try setting a+b to be each divisors not larger than sqrt(n), binary search for a and b. We can use binary search because the directional derivative along a+b=c of a^2+b^2-ab is monotonic. We can also throw away divisors that are too small and too large.

Beyond this level (roughly O(factorization(n) or O(divisor(n)), see the other answer for a more clever manipulation) it seems very hard to make good theoretical progress on this. See this

Upvotes: 0

Miguel Velilla
Miguel Velilla

Reputation: 141

I posted this also in StackExchange, so sorry if you consider duplicate, but I really don´t know if these are the same or different boards (Exchange and Overflow). My profile appears different here.

==========================

There is a faster algorithm to check if a given integer is a sum (or difference) of two cubes n=a^3+b^3

I don´t know if this algorithm is already known (probably yes, but I can´t find it on books or internet). I discovered and use it to compute integers until n < 10^18

This process uses a single trick

4(a^3+b^3)/(a+b) = (a+b)^2 + 3(a-b)^2)

We don´t know in advance what would be "a" and "b" and so what also would be "(a+b)", but we know that "(a+b)" should certainly divide (a^3+b^3) , so if you have a fast primes factorizing routine, you can quickly compute each one of divisors of (a^3+b^3) and then check if

(4(a^3+b^3)/divisor - divisor^2)/3 = square

When (and if) found a square, you have divisor=(a+b) and sqrt(square)=(a-b) , so you have a and b.

If not square found, the number is not sum of two cubes.

We know divisor < (4(a^3+b^3)^(1/3) and this limit improves the task, because when you are assembling divisors of (a^3+b^3) immediately discard those greater than limit.

Now some comparisons with other algorithms - for n = 10^18, by using brute force you should test all numbers below 10^6 to know the answer. On the other hand, to build all divisors of 10^18 you need primes until 10^9.

The max quantity of different primes you could fit into 10^9 is 10 (2*3*5*7*11*13*17*19*23*29 = 5*10^9) so we have 2^10-1 different combinations of primes (which assemble the divisors) to check in worst case, many of them discared because limit.

To compute prime factors I use a table with first 60.000.000 primes which works very well on this range.

Miguel Velilla

Upvotes: 4

user448810
user448810

Reputation: 17866

To find all the pairs of integers x and y that sum to n when cubed, set x to the largest integer less than the cube root of n, set y to 0, then repeatedly add 1 to y if the sum of the cubes is less than n, subtract 1 from x if the sum of the cubes is greater than n, and output the pair otherwise, stopping when x and y cross. If you only want to know whether or not such a pair exists, you can stop as soon as you find one.

Let us know if you have trouble coding this algorithm.

Upvotes: 1

Related Questions