# Counting the positive integer solutions of an equation

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?

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

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