Different ways of representing N as K non-zero integers

The question "Different ways of representing N as K non-zero integers" has applications in many real-world use cases.

Cryptography - In cryptography, specific encryption methods are designed using the concept of encoding a number N as the sum of K non-zero integers.

Representing an integer N as the sum of K non-zero integers may appear in sub-problems of different optimization problems of the optimization method.

Machine Learning− In machine learning, feature vectors describing the distribution of data points can be created by using the problem of representing an integer N as the sum of K non-zero integers.

The Chinese translation of

Explanation

is:

Explanation

Now let’s decode the problem.

Suppose we have two positive integers N and K, and we need to find K non-zero integers whose sum is equal to N. For example, if N=10 and K=3, we need to find three non-zero integers whose sum equals 10. Possible solutions in this case are −

1 + 4 + 5
2 + 3 + 5
2 + 4 + 4

Note that in these solutions we have K=3 non-zero integers, which add up to N=10.

There are different ways to solve this problem, let's discuss each one.

Recursive method

Use a step-by-step algorithm of the recursive method to find different ways of representing N with K non-zero integers.

• Enter the values ​​of N and K in the main function.

• Create a function f(N, K), which returns the total number of ways N can be expressed as K non-zero integers.

• If K = 1, return 1 when N exceeds 0, otherwise return 0. (basic situation).

• If N == 0 or K > N, return 0. (basic situation).

• Create a variable count to store the results.

• Set the value of variable count to 0.

• From 1 to min(N-K 1, N-1) for each integer I

• Recursively calculate f (N-i, K-1).

• Add the result to the count.

• Return the count.

Example

Implementation of the above algorithm

#include <iostream>
using namespace std;

int f(int N, int K) {
   if (K == 1) {
      return (N > 0) ? 1 : 0; // base case
   }
   if (N <= 0 || K > N) {
      return 0; // base case
   }
   int count = 0;
   for (int i = 1; i <= min(N-K+1, N-1); i++) {
      count += f(N-i, K-1);
   }
   return count;
}

int main() {
   int N = 5, K = 2;
   
   int ways = f(N, K);
   cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
   return 0;
}

Output

Number of ways to represent 5 as the sum of 2 non-zero integers: 4

Complexity

Time complexity: O(N ^ K).

Space complexity: O(K)

Binomial coefficient formula

The stars and stripes combination method can be used to obtain a formula for the way in which a positive integer N can be expressed as the sum of K non-zero integers.

Imagine a row of N stars (*), which represent N partition units of a given integer. You can use K-1 vertical bars (|) to arrange the stars into K segments, representing K non-zero integers of the partition.

Take dividing 10 into 3 non-zero integers as an example. The following asterisks and dashes can be used to indicate this process −

* * | * * * | * * * * *

The first part of this illustration depicts the number 2, the second part depicts the number 3, and the third part depicts the number 5.

The number of ways to arrange K-1 bars in a row of N stars is equal to the number of ways to represent N with K non-zero integers. To calculate this quantity, we use the formula: $\mathrm{C(N\: \:K\:-\:1,\:K\:-\:1)}$.

According to the binomial coefficient formula $\mathrm{C(n,k)\:=\:n!\:/(k!*(n-k)!)}$.

But in our case, we need to exclude the possibility of containing 0. To exclude divisions that contain 0 as one of the addends, we can use the following method −

• Subtract 1 from N to get N-1.

• Divide N-1 into K-1 non-negative integers.

• Add 1 to all the K-1 non-negative integers obtained in step 2 to obtain K non-zero integers, and their sum is N.

The reason this method works is that the smallest possible value of each addend is 1 (because we want it to be a non-zero integer), so we subtract 1 from N to ensure that there are enough units to allocate to the K addends number.

Therefore, we get the formula: ways = C(N-1, K-1)

Suppose we want to find the number of ways to represent 6 with 4 non-zero integers. We can use the formula derived previously, i.e. −

C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10

This tells us that there are 10 ways to divide 6 into 4 non-zero integers.

They are −

• 1 1 1 3

• 1 1 2 2

• 1 1 3 1

• 1 2 1 2

• 1 2 2 1

• 1 3 1 1

• 2 1 1 2

• 2 1 2 1

• 2 2 1 1

• 3 1 1 1

method

Let us discuss the step-by-step algorithm for implementing the above method -

• Enter the values ​​of N and K in the main function.

• Calculate the number of methods using the formula above.

• Print out the value of the variable ways.

Now let's write some code.

Example

Code implementation using binomial coefficient method

#include <iostream>
using namespace std;

int binomial(int n, int k) {
   int res = 1;
   if (k > n - k) {
      k = n - k;
   }
   for (int i = 0; i < k; ++i) {
      res *= (n - i);
      res /= (i + 1);
   }
   return res;
}

int main() {
   int N = 7, K = 2;
   
   int ways = binomial(N - 1, K - 1);
   cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
   return 0;
}

Output

Number of ways to represent 7 as the sum of 2 non-zero integers: 6

Complexity

Time complexity: O( K).

Space complexity: O(1)

in conclusion

In this article, we try to explain a way to find out how to represent N as the sum of K non-zero integers. I hope this article helped you understand this concept better.

The above is the detailed content of Different ways of representing N as K non-zero integers. For more information, please follow other related articles on the PHP Chinese website!