Tutorialspoint.dev

Sum of all elements up to Nth row in a Pascal triangle

Given a row number n, and the task is to calculate the sum of all elements of each row up to nth row.

Examples:

Input  : 2
Output : 7 
Explanation:  row 0 have element 1
              row 1 have elements 1, 1
              row 2 have elements 1, 2, 1
              so, sum will be ((1) + (1 + 1) + (1 + 2 + 1)) = 7

Input  : 4
Output : 31
Explanation:  row 0 have element 1
              row 1 have elements 1, 1
              row 2 have elements 1, 2, 1
              row 3 have elements 1, 3, 3, 1
              row 4 have elements 1, 4, 6, 4, 1
              so, sum will be ((1) + (1 + 1) + (1 + 2 + 1)
              + (1 + 3 + 3 + 1) + (1 + 4 + 6 + 4 + 1)) = 31

Below is the example of Pascal triangle having 11 rows:

                             Pascal's triangle
                                                                  
0th row                             1                                
1st row                           1   1                              
2nd row                         1   2   1                            
3rd row                       1   3   3   1                          
4th row                     1   4   6   4   1                        
5th row                   1   5   10  10  5   1                     
6th row                 1   6   15  20  15  6   1                   
7th row               1   7   21  35  35  21  7   1                  
8th row             1  8   28   56  70   56  28  8  1                
9th row           1   9  36  84  126  126  84  36  9  1              
10th row        1  10  45  120 210  256  210 120 45 10  1            

Naive Approach: In a Pascal triangle, each entry of a row is value of binomial coefficient. So a simple solution is to generating all row elements up to nth row and adding them. But this approach will have O(n3) time complexity. However, it can be optimized up to O(n2) time complexity. Refer the following article to generate elements of Pascal’s triangle:

Better Solution: Let’s have a look on pascal’s triangle pattern



                                                               sum of elements in ith row
0th row                             1                                1    -> 20
1st row                           1   1                              2    -> 21
2nd row                         1   2   1                            4    -> 22
3rd row                       1   3   3   1                          8    -> 23
4th row                     1   4   6   4   1                        16   -> 24
5th row                   1   5   10  10  5   1                      32   -> 25
6th row                 1   6   15  20  15  6   1                    64   -> 26
7th row               1   7   21  35  35  21  7   1                  128  -> 27
8th row             1  8   28   56  70   56  28  8  1                256  -> 28
9th row           1   9  36  84  126  126  84  36  9  1              512  -> 29
10th row        1  10  45  120 210  256  210 120 45 10  1            1024 -> 210

As shown above, the sum of elements in the ith row is equal to 2i. Now it can be easily calculated the sum of all elements up to nth row by adding powers of 2.

Below is the implementation of above approach:

C++

// C++ program to find sum of all elements
// upto nth row in Pascal triangle.
#include <bits/stdc++.h>
using namespace std;
  
// Function to find sum of aal elements
// upto nth row.
long long int calculateSum(int n)
{
  
    // Initialize sum with 0
    long long int sum = 0;
  
    // Loop to calculate power of 2
    // upto n and add them
    for (int row = 0; row < n; row++) {
        sum = sum + (1 << row);
    }
  
    return sum;
}
  
// Driver function
int main()
{
    int n = 10;
    cout << " Sum of all elements:" << calculateSum(n);
    return 0;
}

Java

// Java program to find sum of all elements
// upto nth row in Pascal triangle.
import java.io.*;
  
class GFG {
  
    // Function to find sum of aal elements
    // upto nth row.
    static long calculateSum(int n)
    {
  
        // Initialize sum with 0
        long sum = 0;
  
        // Loop to calculate power of 2
        // upto n and add them
        for (int row = 0; row < n; row++) {
            sum = sum + (1 << row);
        }
  
        return sum;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int n = 10;
        System.out.println("Sum of all elements:"
                           + calculateSum(n));
    }
}

Python3

# Python program to find sum of all elements
# upto nth row in Pascal triangle.
  
# Function to find sum of aal elements
# upto nth row.
def calculateSum(n) :
          
    # Initialize sum with 0
    sum = 0
      
    # Loop to calculate power of 2
    # upto n and add them
    for row in range(n):
        sum = sum + (1 << row)
  
    return sum
      
# Driver code    
n = 10
print("Sum of all elements:", calculateSum(n))

C#

// C# program to find sum of all elements
// upto nth row in Pascal triangle.
using System;
  
public class GFG {
  
    // Function to find sum of aal elements
    // upto nth row.
    static long calculateSum(int n)
    {
  
        // Initialize sum with 0
        long sum = 0;
  
        // Loop to calculate power of 2
        // upto n and add them
        for (int row = 0; row < n; row++) {
            sum = sum + (1 << row);
        }
  
        return sum;
    }
  
    static public void Main()
    {
        int n = 10;
        Console.WriteLine("Sum of all elements:"
                          + calculateSum(n));
    }
}

PHP

<?php
// PHP program to find sum of 
// all elements upto nth row 
// in Pascal triangle.
  
// Function to find sum of 
// all elements upto nth row.
function calculateSum($n)
{
  
    // Initialize sum with 0
    $sum = 0;
  
    // Loop to calculate power 
    // of 2 upto n and add them
    for ($row = 0; $row < $n; $row++) 
    {
        $sum = $sum + (1 << $row);
    }
  
    return $sum;
}
  
// Driver Code
$n = 10;
echo " Sum of all elements : "
               calculateSum($n);
  
// This code is contributed by Mahadev.
?>

Output:

Sum of all elements:1023

Time complexity: O(n)

Efficient solution:

2n can be expressed as
2n = ( 20 + 21 + 22 + 23 +. . . + 2(n-1) ) + 1

For Example:
26 = ( 20 + 21 + 22 + 23 + 24 + 25 ) + 1
64 = ( 1 + 2 + 4 + 8 +16 + 32 ) + 1
64 = 63 + 1

So, calculate 2n instead of calculating every power of 2 up to (n – 1) and from above example the sum of the power of 2 up to (n – 1) will be (2n – 1).

C++

// C++ program to find sum of all elements
// upto nth row in Pascal triangle.
#include <bits/stdc++.h>
using namespace std;
  
// Function to find sum of aal elements
// upto nth row.
long long int calculateSum(int n)
{
  
    // Initialize sum with 0
    long long int sum = 0;
  
    // Calculate 2^n
    sum = 1 << n;
  
    return (sum - 1);
}
  
// Driver function
int main()
{
  
    int n = 10;
    cout << " Sum of all elements:" << calculateSum(n);
    return 0;
}

Java

// Java program to find sum of all elements
// upto nth row in Pascal triangle.
import java.io.*;
  
class GFG {
  
    // Function to find sum of aal elements
    // upto nth row.
    static long calculateSum(int n)
    {
  
        // Initialize sum with 0
        long sum = 0;
  
        // Calculate 2^n
        sum = 1 << n;
  
        return (sum - 1);
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int n = 10;
        System.out.println("Sum of all elements:"
                           + calculateSum(n));
    }
}

Python3

# Python3 program to find sum of all elements
# upto nth row in Pascal triangle.
  
# Function to find sum of aal elements
# upto nth row.
def calculateSum(n) :
      
    # Initialize sum with 0
    sum = 0
      
    # Calculate 2 ^ n
    sum = 1 << n;
      
    return (sum - 1)
  
# Driver unicode
n = 10
print("Sum of all elements:", calculateSum(n))

C#

// C# program to find sum of all elements
// upto nth row in Pascal triangle.
using System;
  
public class GFG {
  
    // Function to find sum of aal elements
    // upto nth row.
    static long calculateSum(int n)
    {
  
        // Initialize sum with 0
        long sum = 0;
  
        // Calculate 2^n
        sum = 1 << n;
  
        return (sum - 1);
    }
  
    // Driver code
    static public void Main()
    {
        int n = 10;
        Console.WriteLine("Sum of all elements:"
                          + calculateSum(n));
    }
}

PHP

<?php
// PHP program to find sum
// of all elements upto nth
// row in Pascal triangle.
  
// Function to find 
// sum of all elements
// upto nth row.
  
function calculateSum($n)
{
    // Initialize sum with 0
    $sum = 0;
      
    // Calculate 2^n
    $sum = 1 << $n;
  
    return ($sum - 1);
}
  
// Driver Code
$n = 10;
echo " Sum of all elements:" ,
             calculateSum($n);
  
// This code is contributed 
// by akt_mit
?>

Output:

Sum of all elements:1023

Time complexity: O(1)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter