CODEWITHSUNDEEP
algorithm
Patryk
Patryk

Reputation: 3152

What's the fastest way to find different equations number in integers?

the equation looks like that:

x1 + x2 + x3 + x4 + ... + xk = n

and ( 0 <= n <= 1000, 0 < k <=1000 )

example:

n=3 and k=2

3+0=3 2+1=3
0+3=3 1+2=3

output: 4 // count of equations

I can't think of anything, even the worst 100 loop way to do this.

Upvotes: 4

Views: 135

Answers (3)

ylc
ylc

Reputation: 438

It is more like a math problem.
Suppose you have k-1 |s and n Os. The |s split those Os into k partitions. For example if k = 3 and n = 8 it may be split like this

O O O | O | O O O O

The first partition x1 has 3 Os, the second partition x2 has 1 O, and x3 has 4 Os, that is, 3 + 1 + 4 = 8. So the count of equations is the number of combinations of |s and Os, or C(k + n - 1, n).

Upvotes: 1

Matthew Strawbridge
Matthew Strawbridge

Reputation: 20630

This sounds like the second Stars and Bars theorem.

For any pair of natural numbers k and n, the number of distinct k-tuples of non-negative integers whose sum is n is given by the binomial coefficient (k + n - 1 n)...

(I've swapped n and k from the description in Wikipedia to match your question.)

So, in the example you gave with n=3 and k=2, the answer is (2 + 3 - 1 3) = (4 3) = 4! / ((4 - 3)! × 3!) = 4.

Therefore, if you pre-cache the factorial values you should be able to do the calculation quickly for any of your values of k and n.

Upvotes: 2

Dante May Code
Dante May Code

Reputation: 11247

n = 0 -> 1
k = 1 -> 1
k = 2 -> n + 1
k > 2 -> func(n, k - 1) + func(n - 1, k - 1) + .... + func(0, k - 1)
      // 0 + ...          1 + ...                     n + 0 + ... + 0

thus, do it recursively....

int func(int n, int k) {
    assert (n >= 0);
    assert (k > 0);
    if (n == 0 || k == 1) {
        return 1;
    }
    else if (k == 2) {
        return n + 1;
    }
    else {
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            sum += func(i, k - 1);
        }
        return sum;
    }
}

to eliminate redundant calculation

int result[NMAX + 1][KMAX + 1] = {0};
int func(int n, int k) {
    assert (n >= 0);
    assert (k > 0);
    if (n == 0 || k == 1) {
        return 1;
    }
    else if (k == 2) {
        return n + 1;
    }
    else if (result[n][k] != 0) {
        return result[n][k];
    }
    else {
        int sum = 0;
        for (int i = 0; i <= n; i++) {
            sum += func(i, k - 1);
        }
        result[n][k] = sum;
        return sum;
    }
}

Upvotes: 2

Related Questions