dev.to staff

Posted on Mar 11, 2020

Daily Challenge #203 - Pascal's Triangle

#challenge

In the drawing below we have a part of the Pascal's triangle, lines are numbered from zero (top).

We want to calculate the sum of the squares of the binomial coefficients on a given line with a function called easyline (or easyLine or easy-line).

Can you write a program which calculates easyline(n) where n is the line number?

The function will take n (with: n >= 0) as parameter and will return the sum of the squares of the binomial coefficients on line n.

Examples:

easyline(0) => 1
easyline(1) => 2
easyline(4) => 70
easyline(50) => 100891344545564193334812497256

Tests

easyline(7)
easyline(13)
easyline(3)
easyline(19)

Happy Coding!

This challenge comes from g964 on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (4)

Craig McIlwrath • Mar 12 '20

Haskell:

factorial :: (Integral a) => a -> a
factorial n = product [1..n]

choose :: (Integral a, Num b) => a -> a -> b
n `choose` k = fromIntegral $ factorial n `div` (factorial k * factorial (n - k)) 

easyLine :: (Integral a, Num b) => a -> b
easyLine n = (2 * n) `choose` n

From Wikipedia

The sum of the squares of the elements of row n equals the middle element of row 2n...In general form:

$\sum_{k = 0}^{n} {n \choose k}^2 = {2n \choose n}$

p.s. I got to use the new latex feature for that!

Vidit Sarkar • Mar 11 '20

Python one-liner using recursion

easyLine = lambda n : 1 if n==0 else int((2*(2*n-1)/n)*easyLine(n-1))

Because,

easyLine(n) = 2*(2*n-1)/n * easyLine(n-1) when n > 0
            = 1 when n=0

Vidit Sarkar • Mar 11 '20

C++

// calculate nCr in O(r) time
long long binCoef(int n, int r){
    r = min(r, n-r);
    int ans = 1;
    for(int i=0;i<r;i++){
        ans *= (n-i);
        ans /= i+1;
    }
    return ans;
}

// calculate the sum
// sum will be 2nCn
// O(n) solution
long long easyline(int n){
    return binCoef(2*n, n);
}

InsoGamer • Mar 12 '20

Little lazy solution using 11 in python3

def easyLine(n):
    if n<0:
        return
    print (sum( [ int(i)**2 for i in str(11**n)] ))

DEV Community

Daily Challenge #203 - Pascal's Triangle

Examples:

Tests

Top comments (4)

Read next

The Big Power of Small Pull Requests

Day 4: Our First Python Program | 100 Days Python

PAPPL Scan API Bridging: GSoC 2024 Project Report 🖨️🧑‍💻

How to configure TSC + Webpack + ESM for NodeJS