Sum of sum of all subsets of a set formed by first N natural numbers

0 0 9 minutes read

Given N, and ff(N) = f(1) + f(2) + …… + f(N), where f(k) is the sum of all subsets of a set formed by first k natural numbers. The task is to find ff(N) modulo 1000000007.

Examples:

Input: 2
Output: 7
f(1) + f(2)
f(1) = 1 = 1
f(2) = 1 + 2 + {1 + 2} = 6

Input: 3
Output: 31
f(1) + f(2) + f(3)
f(1) = 1 = 1
f(2) = 1 + 2 + {1 + 2} = 6
f(3) = 1 + 2 + 3 + {1 + 2} + {2 + 3} + {1 + 3} + {1 + 2 + 3} = 24

Approach: Find a pattern of the sequence that will form. The values of f(1), f(2), f(3) are 1, 6 and 31 respectively. Let’s find f(4).

f(4) =  1 + 2 + 3 + 4 + {1 + 2} + {1 + 3} + {1 + 4} 
        + {2 + 3} + {2 + 4} + {3 + 4} + {1 + 2 + 3} + {1 + 2 + 4}
        + {1 + 3 + 4} + {2 + 3 + 4} + {1 + 2 + 3 + 4} = 80.

Hence ff(N) will be

ff(1) = f(1) = 1
ff(2) = f(1) + f(2) = 7
ff(3) = f(1) + f(2) + f(3) = 31
ff(4) = f(1) + f(2) + f(3) + f(4) = 111
.
.
.

The series formed is 1, 7, 31, 111… There exists a formula for it which is 2^n*(n^2 + n + 2) – 1. where, N is starting from zero.
Below is the implementation of the above approach.

C++

// C++ program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
#include <bits/stdc++.h>
using namespace std;
 
// modulo value
#define mod (int)(1e9 + 7)
 
// Iterative Function to calculate (x^y)%p in O(log y)
int power(int x, int y, int p)
{
    int res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0) {
 
        // If y is odd, multiply x with the result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// function to find ff(n)
int check(int n)
{
    // In formula n is starting from zero
    n--;
 
    // calculate answer using
    // formula 2^n*(n^2 + n + 2) - 1
    int ans = n * n;
 
    // whenever answer is greater than
    // or equals to mod then modulo it.
    if (ans >= mod)
        ans %= mod;
 
    ans += n + 2;
 
    if (ans >= mod)
        ans %= mod;
 
    ans = (power(2, n, mod) % mod * ans % mod) % mod;
 
    // adding modulo while subtraction is very necessary
    // otherwise it will cause wrong answer
    ans = (ans - 1 + mod) % mod;
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 4;
 
    // function call
    cout << check(n) << endl;
 
    return 0;
}

C

// C program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
#include <stdio.h>
 
// modulo value
#define mod (int)(1e9 + 7)
 
// Iterative Function to calculate (x^y)%p in O(log y)
int power(int x, int y, int p)
{
    int res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0) {
 
        // If y is odd, multiply x with the result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// function to find ff(n)
int check(int n)
{
    // In formula n is starting from zero
    n--;
 
    // calculate answer using
    // formula 2^n*(n^2 + n + 2) - 1
    int ans = n * n;
 
    // whenever answer is greater than
    // or equals to mod then modulo it.
    if (ans >= mod)
        ans %= mod;
 
    ans += n + 2;
 
    if (ans >= mod)
        ans %= mod;
 
    ans = (power(2, n, mod) % mod * ans % mod) % mod;
 
    // adding modulo while subtraction is very necessary
    // otherwise it will cause wrong answer
    ans = (ans - 1 + mod) % mod;
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 4;
 
    // function call
    printf("%d\n",check(n));
 
    return 0;
}
 
// This code is contributed by kothavvsaakash.

Java

// Java program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
  
class Geeks {
      
// Iterative Function to calculate
// (x^y)%p in O(log y)
static int power(int x, int y, int p)
{
     
    // Initialize result
    int res = 1; 
  
    // Update x if it is more 
    // than or equal to p
    x = x % p; 
  
    while (y > 0) {
  
        // If y is odd, multiply x
        // with the result
        if (y != 0)
            res = (res * x) % p;
  
        // y must be even now
        // y = y / 2
        y = y >> 1; 
        x = (x * x) % p;
    }
    return res;
}
  
// function to find ff(n)
static int check(int n)
{
      
    // modulo value
    int  mod = (int)(1e9 + 7);
  
    // In formula n is 
    // starting from zero
    n--;
  
    // calculate answer using
    // formula 2^n*(n^2 + n + 2) - 1
    int ans = n * n;
  
    // whenever answer is greater than
    // or equals to mod then modulo it.
    if (ans >= mod)
        ans %= mod;
  
    ans += n + 2;
  
    if (ans >= mod)
        ans %= mod;
  
    ans = (power(2, n, mod) % mod *
                  ans % mod) % mod;
  
    // adding modulo while subtraction
    // is very necessary otherwise it 
    // will cause wrong answer
    ans = (ans - 1 + mod) % mod;
  
    return ans;
}
  
// Driver Code
public static void main(String args[])
{
    int n = 4;
  
    // function call
    System.out.println(check(n));
}
}
  
// This code is contributed by ankita_saini

Python3

#Python3 program to find Sum of all 
# subsets of a set formed by 
# first N natural numbers | Set-2 
 
 
 
# modulo value 
mod = (int)(1e9 + 7) 
 
# Iterative Function to calculate (x^y)%p in O(log y) 
def power(x,y,p): 
    res = 1 # Initialize result 
 
    x = x % p # Update x if it is more than or 
    # equal to p 
 
    while (y > 0):
 
        # If y is odd, multiply x with the result 
        if (y & 1): 
            res = (res * x) % p 
 
        # y must be even now 
        y = y >> 1 # y = y/2 
        x = (x * x) % p 
    return res 
 
# function to find ff(n) 
def check(n): 
    # In formula n is starting from zero 
    n=n-1
 
    # calculate answer using 
    # formula 2^n*(n^2 + n + 2) - 1 
    ans = n * n 
 
    # whenever answer is greater than 
    # or equals to mod then modulo it. 
    if (ans >= mod): 
        ans %= mod 
 
    ans += n + 2
 
    if (ans >= mod): 
        ans %= mod 
 
    ans = (pow(2, n, mod) % mod * ans % mod) % mod 
 
    # adding modulo while subtraction is very necessary 
    # otherwise it will cause wrong answer 
    ans = (ans - 1 + mod) % mod 
 
    return ans 
 
#Driver code 
if __name__=='__main__':
    n = 4
 
# function call 
    print(check(n)) 
 
# This code is contributed by ash264

C#

// C# program to find Sum 
// of all subsets of a set 
// formed by first N natural
// numbers | Set-2
using System;
 
class GFG
{
     
// Iterative Function 
// to calculate (x^y)%p 
// in O(log y)
static int power(int x, int y,
                 int p)
{
     
    // Initialize result
    int res = 1; 
 
    // Update x if it is more 
    // than or equal to p
    x = x % p; 
 
    while (y > 0) 
    {
 
        // If y is odd, multiply 
        // x with the result
        if (y != 0)
            res = (res * x) % p;
 
        // y must be even 
        // now y = y / 2
        y = y >> 1; 
        x = (x * x) % p;
    }
    return res;
}
 
// function to find ff(n)
static int check(int n)
{
     
    // modulo value
    int mod = (int)(1e9 + 7);
 
    // In formula n is 
    // starting from zero
    n--;
 
    // calculate answer 
    // using formula 
    // 2^n*(n^2 + n + 2) - 1
    int ans = n * n;
 
    // whenever answer is 
    // greater than or equals 
    // to mod then modulo it.
    if (ans >= mod)
        ans %= mod;
 
    ans += n + 2;
 
    if (ans >= mod)
        ans %= mod;
 
    ans = (power(2, n, mod) % mod *
                 ans % mod) % mod;
 
    // adding modulo while 
    // subtraction is very 
    // necessary otherwise it 
    // will cause wrong answer
    ans = (ans - 1 + mod) % mod;
 
    return ans;
}
 
// Driver Code
public static void Main(String []args)
{
    int n = 4;
 
    // function call
    Console.WriteLine(check(n));
}
}
 
// This code is contributed
// by ankita_saini

PHP

<?php
// PHP program to find Sum 
// of all subsets of a set 
// formed by first N natural 
// numbers | Set-2
 
// modulo value
 
// Iterative Function to
// calculate (x^y)%p in O(log y)
function power($x, $y, $p)
{
    $res = 1; // Initialize result
 
    $x = $x % $p; // Update x if it 
                  // is more than or
                  // equal to p
 
    while ($y > 0)
    {
 
        // If y is odd, multiply
        // x with the result
        if ($y & 1)
            $res = ($res * $x) % $p;
 
        // y must be even now
        $y = $y >> 1; // y = y/2
        $x = ($x * $x) % $p;
    }
    return $res;
}
 
// function to find ff(n)
function check($n)
{
    $mod = 1e9+7;
     
    // In formula n is 
    // starting from zero
    $n--;
 
    // calculate answer using
    // formula 2^n*(n^2 + n + 2) - 1
    $ans = $n * $n;
 
    // whenever answer is greater 
    // than or equals to mod then
    // modulo it.
    if ($ans >= $mod)
        $ans %= $mod;
 
    $ans += $n + 2;
 
    if ($ans >= $mod)
        $ans %= $mod;
 
    $ans = (power(2, $n, $mod) %
                   $mod * $ans % 
                   $mod) % $mod;
 
    // adding modulo while subtraction 
    // is very necessary otherwise it
    // will cause wrong answer
    $ans = ($ans - 1 + $mod) % $mod;
 
    return $ans;
}
 
// Driver code
$n = 4;
 
// function call
echo check($n) ."\n";
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
// javascript program to find Sum of all
// subsets of a set formed by
// first N natural numbers | Set-2
 
// modulo value
const mod = (1e9 + 7);
 
// Iterative Function to calculate (x^y)%p in O(log y)
function power( x,  y,  p)
{
    let res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0)
    {
 
        // If y is odd, multiply x with the result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// function to find ff(n)
function check( n)
{
 
    // In formula n is starting from zero
    n--;
 
    // calculate answer using
    // formula 2^n*(n^2 + n + 2) - 1
    let ans = n * n;
 
    // whenever answer is greater than
    // or equals to mod then modulo it.
    if (ans >= mod)
        ans %= mod;
    ans += n + 2;
    if (ans >= mod)
        ans %= mod;
 
    ans = (power(2, n, mod) % mod * ans % mod) % mod;
 
    // adding modulo while subtraction is very necessary
    // otherwise it will cause wrong answer
    ans = (ans - 1 + mod) % mod;
 
    return ans;
}
 
// Driver code
    let n = 4;
 
    // function call
     document.write(check(n));
 
// This code is contributed by aashish1995 
</script>

Output:

Time complexity: O(log n).
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!