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} = 6Input: 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 codeint 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 codeint 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 Codepublic 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-2using 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 Codepublic 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 callecho 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 valueconst 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:
111
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
