1
\$\begingroup\$

Purpose

Implement a solution that returns the values in the Nth row of Pascal's Triangle where N >= 0.

Math

First three rows of Pascal's Triangle: 1 1 1 1 2 1 ... ...

These row values can be calculated by the following methodology:

  • For a given non-negative row index, the first row value will be the binomial coefficient where n is the row index value and k is 0).
  • The next row value would be the binomial coefficient with the same n-value (the row index value) but incrementing the k-value by 1, until the k-value is equal to the row index value.

Implementation

There are two things the calculator would need in order to operate correctly:

  • A Binomial Coefficient Calculator, which it would depend on directly
  • A Factorial Calculator, which the Binomial Coefficient Calculator would depend on directly
public class FactorialCalculator {

  public static int calculateFactorial(int n) {
    if (n < 0) {
      throw new IllegalArgumentException("n value should be non-negative");
    }

    int factorialValue = 1;

    if (n == 0) {
      return factorialValue;
    }

    for (int multiplier = n; multiplier > 0; multiplier--) {
      factorialValue *= multiplier;
    }

    return factorialValue;
  }
}

public class BinomialCoefficientCalculator {

  public static int calculateBinomialCoefficient(int n, int k) {
    if (n < 0) {
      throw new IllegalArgumentException("n value cannot be negative");
    }

    if (k < 0) {
      throw new IllegalArgumentException("k value cannot be negative");
    }

    if (n < k) {
      throw new IllegalArgumentException("n value cannot be less than k value");
    }

    return FactorialCalculator.calculateFactorial(n) / (FactorialCalculator.calculateFactorial(k) * FactorialCalculator.calculateFactorial(n - k));
  }
}

public class PascalsTriangleRowValuesCalculator {

  public static List<Integer> calculateRowValues(int rowIndex) {
    if (rowIndex < 0) {
      throw new IllegalArgumentException("row index must be non-negative");
    }

    List<Integer> rowValues = new ArrayList<>();
    for (int k = 0; k <= rowIndex; k++ ) {
      rowValues.add(BinomialCoefficientCalculator.calculateBinomialCoefficient(rowIndex, k));
    }
    return rowValues;
  }
}
\$\endgroup\$
4
\$\begingroup\$
  • In case n == 0 the loop body of calculateFactorial wouldn't be executed at all, and factorialValue would remain 1. You may safely remove the special case test.

  • The calculations of the binomial wastes time by recomputing factorials of the same number over and over again. The way the main loop in calculateRowValues is set up exaggerates the problem. Consider precomputing the list of required factorials once.

  • The code begins to fail at fairly small n: \$14!\$ is already beyond the 32-bit range. I recommend drop the factorial approach whatsoever, and compute the next row directly from the previous, using an \$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}\$ identity.

\$\endgroup\$
1
\$\begingroup\$
    for (int k = 0; k <= rowIndex; k++ ) {
      rowValues.add(BinomialCoefficientCalculator.calculateBinomialCoefficient(rowIndex, k));
    }

Your solution is elegant but not very efficient. Note that rowIndex is constant while k only changes by one from iteration to iteration. So make use of that.

    int coefficient = 1;

    int k = 0;
    for (int l = (rowIndex + 1) / 2; k < l; k++) {
        rowValues.add(coefficient);

        // each coefficient = the previous coefficient * n - k / k + 1
        // can't use *= because of integer arithmetic
        // need to multiply before dividing to avoid rounding
        coefficient = (coefficient * (rowIndex - k)) / (k + 1);
    }

    // if there should be a middle coefficient, add it
    // the even rows have an odd number of elements
    if (rowIndex % 2 == 0) {
        rowValues.add(coefficient);
    }

    // the for loop increments before ending, so undo that
    k--;

    // the right half is the mirror image of the left half
    for (; k >= 0; k--) {
        rowValues.add(rowValues.get(k));
    }

This relies on $$ \binom{n}{k+1} = \binom{n}{k} \cdot \frac{n - k}{k + 1} $$

This calculates each value in the row from the previous value for the first half of the row. For the second half, it mirrors the first half.

As a side effect, we no longer need the other two methods that you use. All the logic is in this method. And while integer overflow is still possible, it will no longer start with the fourteenth row. You can do much larger values.

As a side effect, you no longer repeatedly calculate the same factorial values, so no need to memoize.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.