Counting the positive integer solutions of an equation

Question

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?

Answer 1

(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 \$ .