Count ways to express even number ‘n’ as sum of even integers

0 0 6 minutes read

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 10⁹ + 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 = 2⁰
ways(4) = 2 = 2¹
ways(6) = 4 = 2²
ways(8) = 8 = 2³
''
''
''
ways(2 * n) = 2^n-1

Replace n by (m / 2)
=> ways(m) = 2^{m/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)
This article is contributed by Shubham Bansal. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!