Count solutions of a equation with a constraint

Question

How to count the solutions of the equation \$x \cdot y + x \cdot z + y \cdot z = n, (0 \leq n \leq 10^4)\$ with the constraint that \$x \geq y \geq z \geq 0\$ ?

To solve this i've isolated the z value and brute-forced the values of x and y. If the values x,y,z satisfy the constraint and equation than its a valid solution.

#include <stdio.h>

int main () {
    int x,y,z,n,counter;
    while ( scanf("%d", &n), n != -1 ) {

        counter = 0;

        for ( x = n ; x >= 0; --x ) {
            for ( y = x ; y > 0 ; --y ) {
                z = (n - x*y);

                //negative z isn't valid
                if(z < 0)
                    continue;

                z /= (x + y);

                if( z <= y && y <= x && x*y + x*z + y*z == n ) {
                    ++counter;
                }
            }
        }

        printf("%d\n",counter);
    }
    return 0;
}

The input contains several lines with one value for n. The program must stop when this value is -1.

The output is the number of solutions of the equation in separated lines.

Sample Input:

20
1
9747
-1

Sample Output:

5
1
57

How to make this code faster ?

Answer 1

Repeating work

Suppose one test case were 9747 and another test case were 9748. Right now, you do the full work for each test case, throwing away the work done for other test cases. This causes your program to take a long time if there are many large test cases.

There is a way to compute all the answers for each of the 10000 test cases in one computation, so you can immediately find the answer to any test case instantly after that.

Sieve-like algorithm

This algorithm works similar to the Sieve of Eratosthenes. It loops through each (x,y,z) combination and increments count[n] by one. Once that is done, count[n] is the answer for any test case n.

#include <stdio.h>

#define MAX        10000
int counts[MAX+1];

int main(void)
{
    int x, y, z, n;

    // For each (x,y,z) combination, increment counts[n] by one, where
    // n = x*y + x*z + y*z, or in other words: n = x*y + z*(x+y)
    for (x = 0; x <= MAX; x++) {
        for (y = 0; y <= x; y++) {
            int sum = x+y;
            for (z = 0, n = x*y; z <= y && n <= MAX; z++, n += sum) {
                counts[n]++;
            }
        }
    }

    // Read test cases and print out answers.
    do {
        scanf("%d", &n);
        if (n == -1 || n > MAX)
            break;
        printf("%d\n", counts[n]);
    } while(1);

    return 0;
}

Timing comparison

The sieve program takes 0.04 seconds on my computer no matter how many test cases are thrown at it. The original program took 0.03 seconds for the sample input shown (3 test cases), but it took 0.56 seconds to handle a test input of 20 large test cases (9900..9919). So as you can see, the original program is \$O(n)\$ on the number of test inputs when it could be made to be \$O(1)\$ using the sieve method.