Count ways to express even number βnβ as sum of even integers
Given an positive even integer βnβ. Count total number of ways to express βnβ as sum of even positive integers. Output the answer in modulo 109 + 7
Examples:
Input: 6 Output: 4 Explanation There are only four ways to write 6 as sum of even integers: 1. 2 + 2 + 2 2. 2 + 4 3. 4 + 2 4. 6 Input: 8 Output: 8
Approach is to find pattern or recursive function whichever is possible. The approach would be the same as already discussed in βCount ways to express βnβ as sum of odd integersβ. Here the given number is even that means even sum can only be achieved by adding the (n-2)th number as two times. We can notice that (by taking some examples) adding a 2 to a number doubles the count. Let the total number of ways to write βnβ be ways(n). The value of βways(n)β can be written by formula as follows:
ways(n) = ways(n-2) + ways(n-2) ways(n) = 2 * ways(n-2) ways(2) = 1 = 20 ways(4) = 2 = 21 ways(6) = 4 = 22 ways(8) = 8 = 23 '' '' '' ways(2 * n) = 2n-1 Replace n by (m / 2) => ways(m) = 2m/2 - 1
C++
// C++ program to count ways to write // number as sum of even integers #include<iostream> using namespace std; // Initialize mod variable as constant const int MOD = 1e9 + 7; /* Iterative Function to calculate (x^y)%p in O(log y) */ int power( int x, unsigned 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 result if (y & 1) res = (1LL * res * x) % p; // y must be even now y = y>>1; // y = y/2 x = (1LL * x * x) % p; } return res; } // Return number of ways to write 'n' // as sum of even integers int countEvenWays( int n) { return power(2, n/2 - 1, MOD); } // Driver code int main() { int n = 6; cout << countEvenWays(n) << "\n" ; n = 8; cout << countEvenWays(n); return 0; } |
Java
// JAVA program to count ways to write // number as sum of even integers class GFG { // Initialize mod variable as constant static int MOD = 1000000007 ; /* 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 result if (y % 2 == 1 ) res = ( 1 * res * x) % p; // y must be even now y = y >> 1 ; // y = y/2 x = ( 1 * x * x) % p; } return res; } // Return number of ways to write // 'n' as sum of even integers static int countEvenWays( int n) { return power( 2 , n/ 2 - 1 , MOD); } // Driver code public static void main(String args[]) { int n = 6 ; System.out.println(countEvenWays(n)); n = 8 ; System.out.println(countEvenWays(n)); } } /* This code is contributed by Nikita Tiwari. */ |
Python
# PYTHON program to count ways to write # number as sum of even integers # Initialize mod variable as constant MOD = 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 result if (y & 1 ) : res = ( 1 * res * x) % p # y must be even now y = y >> 1 # y = y/2 x = ( 1 * x * x) % p return res # Return number of ways to write 'n' # as sum of even integers def countEvenWays(n) : return power( 2 , n / 2 - 1 , MOD) # Driver code n = 6 print ( int (countEvenWays(n))) n = 8 print ( int (countEvenWays(n))) # This code is contributed by Nikita Tiwari. |
C#
// C# program to count ways to write // number as sum of even integers using System; class GFG { // Initialize mod variable as constant static int MOD = 1000000007; /* 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 result if (y % 2 == 1) res = (1 * res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (1 * x * x) % p; } return res; } // Return number of ways to write // 'n' as sum of even integers static int countEvenWays( int n) { return power(2, n/2 - 1, MOD); } // Driver code public static void Main() { int n = 6; Console.WriteLine(countEvenWays(n)); n = 8; Console.WriteLine(countEvenWays(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to count ways // to write number as sum of // even integers // Initialize mod variable // as constant $MOD = 1000000000.0; /* Iterative Function to calculate (x^y)%p in O(log y) */ function power( $x , $y , $p ) { // Initialize result $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 result if ( $y & 1) $res = (1 * $res * $x ) % $p ; // y must be even now $y = $y >> 1; // y = y/2 $x = (1 * $x * $x ) % $p ; } return $res ; } // Return number of ways // to write 'n' as sum of // even integers function countEvenWays( $n ) { global $MOD ; return power(2, $n / 2 - 1, $MOD ); } // Driver code $n = 6; echo countEvenWays( $n ), "\n" ; $n = 8; echo countEvenWays( $n ); // This code is contributed // by ajit ?> |
Javascript
<script> // Javascript program to count ways to write // number as sum of even integers // Initialize mod variable as constant let MOD = 1000000007; /* Iterative Function to calculate (x^y)%p in O(log y) */ function power(x, y, p) { // Initialize result let 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 result if (y % 2 == 1) res = (1 * res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (1 * x * x) % p; } return res; } // Return number of ways to write // 'n' as sum of even integers function countEvenWays(n) { return power(2, n/2 - 1, MOD); } // Driver code let n = 6; document.write(countEvenWays(n) + "<br/>" ); n = 8; document.write(countEvenWays(n)); // This code is contributed by code_hunt. </script> |
Output:
4 8
Time complexity: O(Log(n))
Auxiliary space: O(1)