(JAVA)Binomial Coefficients without overflow


  • 0

    May not be the best idea, but a straight thinking is to calculate binomial coefficients.
    e.g: input 4, the answer is 1, 4, 6, 4, 1 came from C(4,0) C(4,1) ... C(4, 4)

    I try to write a method to calculate binomial coefficients but it easily overflows. Hereby the final acceptted version.

    public class Solution {
        public List<Integer> getRow(int rowIndex) {
            List<Integer> res = new ArrayList<Integer>();
            for (int i = 0; i <= rowIndex; i++) res.add((int)BC(rowIndex, i));
            return res;
        }
        
        public long BC(int n, int m) {
            long res = 1;
            int large = Math.max(n - m, m), small = Math.min(n - m, m);
            for (int i = n; i > large; i--) {
                res *= i;
                res /= small - (i - large) + 1;
            }
            return res;
        }
    }
    

    explaination:

    • We cannot just calculate factors and divide them in generating results, because it is too easy to get overflowed even using long.
    • Thus we need to calculate BC straightly.
    • C(a, b) = a! / (b! * (a - b)!)
    • define large and small as larger and smaller number in b and (a - b), thus C(a, b) = a! / (large! * small!)
    • then calculate multiplications in C(a, b) decreasingly:
      a * a - 1 * ... * large + 1
    • at the same time calculate the left divisions increasingly:
      /1 /2 /.../small
    • multiplications and divisions must in same iteration or multiplications will lead to overflow. divisions must be increasingly or sometimes it is not divisible.
      (e.g: C(5,2) - large = 3, small = 2.
      C(5,2) = (5 * 4) / 2 / 1
      the correct calculation is (5 / 1) * (4 / 2) = 10
      if divide 2 at first, (5 / 2) * (4 / 1) = 8

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.