3
\$\begingroup\$

I have to solve this equation: \$ x + y + xy = n \$

#include <iostream>
#include <cstring>

using namespace std;

long c;

int main()
{
   long x = 0;
   cin >> c;
   if(c == 0)
   {
       cout << 1 << endl;
       return 0;
   }
   for(long i = 1; i <= c / 2; i ++)
   {
       for(long j = 1; j <= c; j ++)
           if(i + j + i * j == c)
           {
                       x ++;
                   break;
           }
   }
   cout << x + 2 << endl;
}

Of course this code is very slow. How can I find a positive number of solutions in a faster way? Maybe there is a specific algorithm?

\$\endgroup\$
  • 1
    \$\begingroup\$ How do you expect to "solve" that equation? It has an infinite number of solutions, which of the solutions do you want to return? \$\endgroup\$ – Simon Forsberg Mar 7 '15 at 12:34
8
\$\begingroup\$

(Remark: The question mentions "positive number of solutions", but from your code I assume that you meant "number of non-negative integer solutions".)

Coding style:

  • #include <cstring> is not needed here.

  • Don't use namespace std;, see for example Why is “using namespace std;” considered bad practice?.

  • long c; is only used in main(), so there is no need at all to declare it as a global variable.

  • Always use braces { ... } for the body of for- and if-statements, even if it has only one statement. It helps to avoid errors if additional statements are added later.

  • Move the computation of the number of solutions to a separate function. This keeps the main function small and is convenient if you add test cases.

  • I prefer a different spacing in for- and if-statements, but that may be a matter of taste.

  • Variable names: If the equation is given as \$ x + y + xy = n \$, then why not use the same names in your program? And x is a quite non-descriptive name of a number of solutions.

  • It may not be immediately obvious why 2 is added to the number of solutions, so an explaining comment would be appropriate here.

Then your code would look like this:

#include <iostream>

// Number of non-negative integer solutions to
//    x + y + x * y == n   .
long numberOfSolutions(long n) {

    if (n == 0) {
        return 1;
    }

    // Count all positive solutions:
    long count = 0;
    for (long x = 1; x <= n / 2; x++) {
        for (long y = 1; y <= n; y++) {
            if (x + y + x * y == n) {
                count++;
                break;
            }
        }
    }
    // Add 2 for the solutions x=0,y=n and x=0,y=n:
    return count + 2;
}

int main()
{
    long n;

    std::cin >> n;
    std::cout << numberOfSolutions(n) << std::endl;
}

Performance:

Your code tries all possible combinations of x, y to find solutions and therefore runs in \$ O(n^2) \$. A small improvement could be to use the symmetry of the problem, i.e. enumerate only pairs with x <= y:

for (long x = 1; x <= n / 2; x++) {
    for (long y = x; y <= n; y++) {
        if (x + y + x * y == n) {
            // Counts a 2 solutions if x != y:
            count = count + 1 + (x != y);
            break;
        }
    }
}

This cuts the total number of iterations down by a factor of 2, but it is still \$ O(n^2) \$.

Better algorithm:

If you write your equation as $$ n + 1 = x + y + xy + 1 = (x + 1)(y + 1) $$ then it becomes obvious that it can be solved by determining the number of divisors of \$ n+1 \$. This known as the Divisor function and can be computed efficiently.

Even the simplest implementation

long numberOfDivisors(long n) {
    long count = 0;

    for (long j = 1; j <= n; j++) {
        if (n % j == 0) {
            count++;
        }
    }
    return count;
}

runs in \$ O(n) \$ instead of \$ O(n^2) \$. More sophisticated methods use the prime factorization of \$ n \$ .

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.