CODEWITHSUNDEEP
arraysalgorithmpascals-trianglebinomial-coefficients
AdamMc331
AdamMc331

Reputation: 16691

Design the binomial coefficient algorithm using a single dimensional array

I have already designed the following algorithm that determines the binomial coefficient using a two dimensional array. For example, to calculate the binomial coefficient of n choose k, we can create a two dimensional array like so:

int[][] arr = new int[n][k];

We can populate the array in the following way:

for(int i = 0; i <= n; i++){
   for(int j = 0; j <= minimum(i, k); j++){
      if(j == 0 || i == j){
         arr[i, j] = 1;
      } else{
         arr[i, j] = arr[i - 1, j - 1] + arr[i - 1, j];
      }
   }
}

However, I need to redesign this algorithm to use a one dimensional array from indexes 0-k. I am having a lot of trouble pinpointing how to do this. I have started in small steps, and realized some common occurrences:

When I say k = 2, this is where it gets tricky, because the value of arr[2] will really depend on the previous values. I believe that as I loop (say from i = 0 to i = n), the values of arr[] will change but I can't quite grasp how. I've started with something along these lines:

for(int i = 0; i <= n; i++){
   for(int j = 0; j <= minimum(i, k); j++){
      if(j == 0 || i == j){
         arr[j] = 1;
      } else if(j == 1){
         arr[j] = i;
      } else{
         arr[j] = ??; // I can't access previous values, because I didn't record them?
      }
   }
}

How should I handle this?

Upvotes: 1

Views: 2024

Answers (1)

kraskevich
kraskevich

Reputation: 18546

Here is a code which uses only one one dimensional array:

int[] coefficients = new int[k + 1];
coefficients[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = k; j >= 1; j--) {
        coefficients[j] += coefficients[j - 1];
    }
}

Why is it correct? To compute coefficients[j] for a fixed i, we need to know the value of coefficients[j - 1] and coefficients[j] for i - 1. If we iterate from k down to 0, we can safely record a new value for the current position because we will never need its old value.

Upvotes: 5

Related Questions