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 ?

• N74: when z<0 you should break
• pjz: @N74 I don't think so - x and y are getting smaller, not larger, so the next pass through the loop should result in a larger z, not a smaller one.
• chux: Should not for ( y = x ; y > 0 ; --y ) { be for ( y = x ; y >= 0 ; --y ) { >= vs > as the condition was "x≥y≥z≥0"?
• Felipe: i don't use y >= 0 because it can cause division by 0 here z /= (x + y). And the case where x = 0 and y = 0 in the formula gives n = 0 (only in this case).
• N74: @pjz I wanted the OP to think about the count in the loop, it he uses the decrement he has to loop for all the elements between x and 0, if he used an increment he could loop only till the condition in the if became true

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.

• chux: Not a fan of this use of the , operator in for(), but am impressed by the sieve of JS1 - nice. (Also suggest test n == -1 --> n < 0)