CODEWITHSUNDEEP
c++algorithm
kevindang
kevindang

Reputation: 37

Exhaustive (brute force) algorithm improvement

I started with the requirements below:

m,n are integers. Search(x,y,z) with

And my code 

for(int x = 1; x<n; x++)
{
   for(int y = 1; y<n; y++)
   {
      for(int z=1; z<n; z++)
      {
         if((x*x*x + y*y*y + z*z+z*z == m) &&(x+y+z==n))
         {
             cout<<x<<"  "<<y<<"  "<<z;
         }
      }
   }
}

And BigO = n^3

With the block code above, the algorithm is very slow. Have you any idea how to boost speed?

Upvotes: 2

Views: 260

Answers (3)

Petr
Petr

Reputation: 9997

You do not need the internal for z loop. Once you have x and y, you can easily determine z as n-x-y. This makes it O(N^2).

UPD: I think you can even make in O(N log N) using binary search approach.

Iterate over x. For a given x, you need to find such y and z that y+z=n-x and y^3+z^3=m-x^3. Assume n'=n-z and m'=m-x^3.

The problem is symmetric with respect to y and z, so we can safely assume y<=z. This makes y<=n'/2.

We need to find such y that y^3+(n'-y)^3=m'. I am almost sure (though not checked this) that the function f(y)=y^3+(n'-y)^3 is monotonic on the [1, n'/2] interval, so you can use binary search to find the root for f(y)=m' equation.

So, for a given x you can find needed y in O(log N) time, which makes O(N log N) running time in total.

Upvotes: 1

marom
marom

Reputation: 5230

This one is O(n^2)

for(int x = 1; x<n; x++)
{
   int n1 = n - x ;
   for(int y = 1; y<n1; y++)
   {
      int z = n - x - y ;
      if (x*x*x + y*y*y+z*z*z==m)
      {
         cout<<x<<"  "<<y<<"  "<<z;
      }
   }
}

Upvotes: 0

Mike Seymour
Mike Seymour

Reputation: 254501

There's no need for the inner loop; given x and y, you can take z = n-x-y. This reduces it to O(n^2).

The second loop only needs to loop while x+y<n, since beyond that there's no positive z such that x+y+z==n. This halves the remaining work.

Once you've done this, there's no need for the second test (since you've already chosen z to make that true); fix the typo in the first test and you get

for (int x = 1; x<n; x++) {
    for (int y = 1; x+y<n; y++) {
        int z = n-x-y;
        if (x*x*x + y*y*y + z*z*z == m) {
            // found it
        }
    }
}

Upvotes: 3

Related Questions