Ways to form an array having integers in given range such that total sum is divisible by 2

19 June 2025

1

Given three positive integers N, L and R. The task is to find the number of ways to form an array of size N where each element lies in the range [L, R] such that the total sum of all the elements of the array is divisible by 2.
Examples:

Input: N = 2, L = 1, R = 3
Output: 5
Explanation: Possible arrays having sum of all elements divisible by 2 are
[1, 1], [2, 2], [1, 3], [3, 1] and [3, 3]
Input: N = 3, L = 2, R = 2
Output: 1

Approach: The idea is to find the count of numbers having remainder 0 and 1 modulo 2 separately lying between L and R. This count can be calculated as follows:

We need to count numbers between range having remainder 1 modulo 2
F = First number in range of required type
L = Last number in range of required type
Count = (L – F) / 2
cnt0, and cnt1 represents Count of numbers between range of each type.

Then, using dynamic programming we can solve this problem. Let dp[i][j] denotes the number of ways where the sum of first i numbers modulo 2 is equal to j. Suppose we need to calculate dp[i][0], then it will have the following recurrence relation: dp[i][0] = (cnt0 * dp[i – 1][0] + cnt1 * dp[i – 1][1]). First term represents the number of ways upto (i – 1) having sum remainder as 0, so we can place cnt0 numbers in i^th position such that sum remainder still remains 0. Second term represents the number of ways upto (i – 1) having sum remainder as 1, so we can place cnt1 numbers in i^th position to such that sum remainder becomes 0. Similarly, we can calculate for dp[i][1].
Final answer will be denoted by dp[N][0].

Steps to solve the problem:

Initialize tL to l and tR to r.
Initialize arrays L and R with 0 for each type (modulo 0 and 1). Set L[l % 2] to l and R[r % 2] to r.
Increment l and decrement r.
If l is less than or equal to tR and r is greater than or equal to tL, set L[l % 2] to l and R[r % 2] to r.
Initialize cnt0 and cnt1 as zero.
If R[0] and L[0] are non-zero, set cnt0 to (R[0] – L[0]) / 2 + 1.
If R[1] and L[1] are non-zero, set cnt1 to (R[1] – L[1]) / 2 + 1.
Initialize a 2D array dp of size n x 2 with all elements set to 0.
Set dp[1][0] to cnt0 and dp[1][1] to cnt1.
For i from 2 to n:
- Set dp[i][0] to cnt0 times dp[i – 1][0] plus cnt1 times dp[i – 1][1].
- Set dp[i][1] to cnt0 times dp[i – 1][1] plus cnt1 times dp[i – 1][0].
Return dp[n][0] as the required count of ways.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
int countWays(int n, int l, int r)
{
    int tL = l, tR = r;
 
    // Represents first and last numbers
    // of each type (modulo 0 and 1)
    int L[2] = { 0 }, R[2] = { 0 };
    L[l % 2] = l, R[r % 2] = r;
 
    l++, r--;
 
    if (l <= tR && r >= tL)
        L[l % 2] = l, R[r % 2] = r;
 
    // Count of numbers of each type between range
    int cnt0 = 0, cnt1 = 0;
    if (R[0] && L[0])
        cnt0 = (R[0] - L[0]) / 2 + 1;
    if (R[1] && L[1])
        cnt1 = (R[1] - L[1]) / 2 + 1;
 
    int dp[n][2];
 
    // Base Cases
    dp[1][0] = cnt0;
    dp[1][1] = cnt1;
    for (int i = 2; i <= n; i++) {
 
        // Ways to form array whose sum upto
        // i numbers modulo 2 is 0
        dp[i][0] = (cnt0 * dp[i - 1][0]
                    + cnt1 * dp[i - 1][1]);
 
        // Ways to form array whose sum upto
        // i numbers modulo 2 is 1
        dp[i][1] = (cnt0 * dp[i - 1][1]
                    + cnt1 * dp[i - 1][0]);
    }
 
    // Return the required count of ways
    return dp[n][0];
}
 
// Driver Code
int main()
{
    int n = 2, l = 1, r = 3;
    cout << countWays(n, l, r);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
static int countWays(int n, int l, int r)
{
    int tL = l, tR = r;
 
    // Represents first and last numbers
    // of each type (modulo 0 and 1)
    int[] L = new int[3];
    int[] R = new int[3];
    L[l % 2] = l;
    R[r % 2] = r;
 
    l++;
    r--;
 
    if (l <= tR && r >= tL)
    {
        L[l % 2] = l;
        R[r % 2] = r;
    }
 
    // Count of numbers of each type between range
    int cnt0 = 0, cnt1 = 0;
    if (R[0] > 0 && L[0] > 0)
        cnt0 = (R[0] - L[0]) / 2 + 1;
    if (R[1] > 0 && L[1] > 0)
        cnt1 = (R[1] - L[1]) / 2 + 1;
 
    int[][] dp = new int[n + 1][3];
 
    // Base Cases
    dp[1][0] = cnt0;
    dp[1][1] = cnt1;
    for (int i = 2; i <= n; i++) 
    {
 
        // Ways to form array whose sum upto
        // i numbers modulo 2 is 0
        dp[i][0] = (cnt0 * dp[i - 1] [0]
                    + cnt1 * dp[i - 1][1]);
 
        // Ways to form array whose sum upto
        // i numbers modulo 2 is 1
        dp[i][1] = (cnt0 * dp[i - 1][1]
                    + cnt1 * dp[i - 1][0]);
    }
 
    // Return the required count of ways
    return dp[n][0];
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 2, l = 1, r = 3;
    System.out.println(countWays(n, l, r));
}
}
 
// This code is contributed by Code_Mech.

Python3

# Python3 implementation of the approach
 
# Function to return the number of ways to
# form an array of size n such that sum of
# all elements is divisible by 2
def countWays(n, l, r):
 
    tL, tR = l, r
 
    # Represents first and last numbers
    # of each type (modulo 0 and 1)
    L = [0 for i in range(2)]
    R = [0 for i in range(2)]
 
    L[l % 2] = l
    R[r % 2] = r
 
    l += 1
    r -= 1
 
    if (l <= tR and r >= tL):
        L[l % 2], R[r % 2] = l, r
 
    # Count of numbers of each type 
    # between range
    cnt0, cnt1 = 0, 0
    if (R[0] and L[0]):
        cnt0 = (R[0] - L[0]) // 2 + 1
    if (R[1] and L[1]):
        cnt1 = (R[1] - L[1]) // 2 + 1
 
    dp = [[0 for i in range(2)] 
             for i in range(n + 1)]
 
    # Base Cases
    dp[1][0] = cnt0
    dp[1][1] = cnt1
    for i in range(2, n + 1):
 
        # Ways to form array whose sum 
        # upto i numbers modulo 2 is 0
        dp[i][0] = (cnt0 * dp[i - 1][0] +
                    cnt1 * dp[i - 1][1])
 
        # Ways to form array whose sum upto
        # i numbers modulo 2 is 1
        dp[i][1] = (cnt0 * dp[i - 1][1] +
                    cnt1 * dp[i - 1][0])
     
    # Return the required count of ways
    return dp[n][0]
 
# Driver Code
n, l, r = 2, 1, 3
print(countWays(n, l, r))
 
# This code is contributed 
# by Mohit Kumar

C#

// C# implementation of the approach
 
using System;
 
class GFG
{
     
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
static int countWays(int n, int l, int r)
{
    int tL = l, tR = r;
 
    // Represents first and last numbers
    // of each type (modulo 0 and 1)
    int[] L = new int[3];
    int[] R = new int[3];
    L[l % 2] = l;
    R[r % 2] = r;
 
    l++;
    r--;
 
    if (l <= tR && r >= tL)
    {
        L[l % 2] = l;
        R[r % 2] = r;
    }
 
    // Count of numbers of each type between range
    int cnt0 = 0, cnt1 = 0;
    if (R[0] > 0 && L[0] > 0)
        cnt0 = (R[0] - L[0]) / 2 + 1;
    if (R[1] > 0 && L[1] > 0)
        cnt1 = (R[1] - L[1]) / 2 + 1;
 
    int[,] dp=new int[n + 1, 3];
 
    // Base Cases
    dp[1, 0] = cnt0;
    dp[1, 1] = cnt1;
    for (int i = 2; i <= n; i++) 
    {
 
        // Ways to form array whose sum upto
        // i numbers modulo 2 is 0
        dp[i, 0] = (cnt0 * dp[i - 1, 0]
                    + cnt1 * dp[i - 1, 1]);
 
        // Ways to form array whose sum upto
        // i numbers modulo 2 is 1
        dp[i, 1] = (cnt0 * dp[i - 1, 1]
                    + cnt1 * dp[i - 1, 0]);
    }
 
    // Return the required count of ways
    return dp[n, 0];
}
 
// Driver Code
static void Main()
{
    int n = 2, l = 1, r = 3;
    Console.WriteLine(countWays(n, l, r));
}
}
 
// This code is contributed by mits

Javascript

<script>
 
    // JavaScript implementation of the approach
     
    // Function to return the number of ways to
    // form an array of size n such that sum of
    // all elements is divisible by 2
    function countWays(n, l, r)
    {
        let tL = l, tR = r;
 
        // Represents first and last numbers
        // of each type (modulo 0 and 1)
        let L = new Array(3);
        let R = new Array(3);
        L[l % 2] = l;
        R[r % 2] = r;
 
        l++;
        r--;
 
        if (l <= tR && r >= tL)
        {
            L[l % 2] = l;
            R[r % 2] = r;
        }
 
        // Count of numbers of each type between range
        let cnt0 = 0, cnt1 = 0;
        if (R[0] > 0 && L[0] > 0)
            cnt0 = (R[0] - L[0]) / 2 + 1;
        if (R[1] > 0 && L[1] > 0)
            cnt1 = (R[1] - L[1]) / 2 + 1;
 
        let dp = new Array(n + 1);
        for (let i = 0; i <= n; i++) 
        {    
            dp[i] = new Array(3);
            for (let j = 0; j < 3; j++) 
            {
                dp[i][j] = 0;
            }
        }
 
        // Base Cases
        dp[1][0] = cnt0;
        dp[1][1] = cnt1;
        for (let i = 2; i <= n; i++) 
        {
 
            // Ways to form array whose sum upto
            // i numbers modulo 2 is 0
            dp[i][0] = (cnt0 * dp[i - 1] [0]
                        + cnt1 * dp[i - 1][1]);
 
            // Ways to form array whose sum upto
            // i numbers modulo 2 is 1
            dp[i][1] = (cnt0 * dp[i - 1][1]
                        + cnt1 * dp[i - 1][0]);
        }
 
        // Return the required count of ways
        return dp[n][0];
    }
     
    let n = 2, l = 1, r = 3;
    document.write(countWays(n, l, r));
     
</script>

PHP

<?php
// PHP implementation of the approach 
 
// Function to return the number of ways to 
// form an array of size n such that sum of 
// all elements is divisible by 2 
function countWays($n, $l, $r) 
{ 
    $tL = $l;
    $tR = $r; 
     
    $L = array_fill(0, 2, 0);
    $R = array_fill(0, 2, 0);
     
    // Represents first and last numbers 
    // of each type (modulo 0 and 1) 
    $L[$l % 2] = $l;
    $R[$r % 2] = $r; 
 
    $l++;
    $r--; 
 
    if ($l <= $tR && $r >= $tL) 
    {
        $L[$l % 2] = $l;
        $R[$r % 2] = $r; 
    }
 
    // Count of numbers of each type
    // between range 
    $cnt0 = 0;
    $cnt1 = 0; 
    if ($R[0] && $L[0]) 
        $cnt0 = ($R[0] - $L[0]) / 2 + 1;
         
    if ($R[1] && $L[1]) 
        $cnt1 = ($R[1] - $L[1]) / 2 + 1; 
 
    $dp = array();
 
    // Base Cases 
    $dp[1][0] = $cnt0; 
    $dp[1][1] = $cnt1; 
    for ($i = 2; $i <= $n; $i++) 
    { 
 
        // Ways to form array whose sum upto 
        // i numbers modulo 2 is 0 
        $dp[$i][0] = ($cnt0 * $dp[$i - 1][0] + 
                      $cnt1 * $dp[$i - 1][1]); 
 
        // Ways to form array whose sum upto 
        // i numbers modulo 2 is 1 
        $dp[$i][1] = ($cnt0 * $dp[$i - 1][1] + 
                      $cnt1 * $dp[$i - 1][0]); 
    } 
 
    // Return the required count of ways 
    return $dp[$n][0]; 
} 
 
// Driver Code 
$n = 2;
$l = 1;
$r = 3; 
 
echo countWays($n, $l, $r); 
 
// This code is contributed by Ryuga
?>

Output

Time Complexity: O(n)
Auxiliary Space: O(n)

Efficient approach : Space optimization O(1)

In previous approach we the current value dp[i] is only depend upon the previous 2 values i.e. dp[i-1][0] and dp[i-1][1]. So to optimize the space we can keep track of previous and current values by the help of three variables prevRow0, prevRow1 and currRow0 , currRow1 which will reduce the space complexity from O(N) to O(1).

Implementation Steps:

Create 2 variables prevRow0 and prevRow1 to keep track of previous values of DP.
Initialize base case prevRow0 = cnt0 , prevRow1 = cnt1. where cnt is Count of numbers of each type between range
Create a variable currRow0 and currRow1 to store current value.
Iterate over subproblem using loop and update curr.
After every iteration update prevRow0 and prevRow1 for further iterations.
At last return prevRow0.

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
int countWays(int n, int l, int r)
{
    int tL = l, tR = r;
 
    // Represents first and last numbers
    // of each type (modulo 0 and 1)
    int L[2] = {0}, R[2] = {0};
    L[l % 2] = l, R[r % 2] = r;
 
    l++, r--;
 
    if (l <= tR && r >= tL)
        L[l % 2] = l, R[r % 2] = r;
 
    // Count of numbers of each type between range
    int cnt0 = 0, cnt1 = 0;
    if (R[0] && L[0])
        cnt0 = (R[0] - L[0]) / 2 + 1;
    if (R[1] && L[1])
        cnt1 = (R[1] - L[1]) / 2 + 1;
 
    // Initialize variables for the first row
    int prevRow0 = cnt0, prevRow1 = cnt1;
 
    // Iterate through the rows and update the previous row values
    for (int i = 2; i <= n; i++) {
        int currRow0 = (cnt0 * prevRow0) + (cnt1 * prevRow1);
        int currRow1 = (cnt0 * prevRow1) + (cnt1 * prevRow0);
        prevRow0 = currRow0;
        prevRow1 = currRow1;
    }
 
    // Return the required count of ways
    return prevRow0;
}
 
// Driver Code
int main()
{
    int n = 2, l = 1, r = 3;
    cout << countWays(n, l, r);
 
    return 0;
}

Java

import java.util.*;
 
public class Main {
    // Function to return the number of ways to
    // form an array of size n such that sum of
    // all elements is divisible by 2
    public static int countWays(int n, int l, int r)
    {
        int tL = l, tR = r;
 
        // Represents first and last numbers
        // of each type (modulo 0 and 1)
        int[] L = new int[2];
        int[] R = new int[2];
        L[l % 2] = l;
        R[r % 2] = r;
 
        l++;
        r--;
 
        if (l <= tR && r >= tL) {
            L[l % 2] = l;
            R[r % 2] = r;
        }
 
        // Count of numbers of each type between range
        int cnt0 = 0, cnt1 = 0;
        if (R[0] != 0 && L[0] != 0) {
            cnt0 = (R[0] - L[0]) / 2 + 1;
        }
        if (R[1] != 0 && L[1] != 0) {
            cnt1 = (R[1] - L[1]) / 2 + 1;
        }
 
        // Initialize variables for the first row
        int prevRow0 = cnt0, prevRow1 = cnt1;
 
        // Iterate through the rows and update the previous
        // row values
        for (int i = 2; i <= n; i++) {
            int currRow0
                = (cnt0 * prevRow0) + (cnt1 * prevRow1);
            int currRow1
                = (cnt0 * prevRow1) + (cnt1 * prevRow0);
            prevRow0 = currRow0;
            prevRow1 = currRow1;
        }
 
        // Return the required count of ways
        return prevRow0;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 2, l = 1, r = 3;
        System.out.println(countWays(n, l, r));
    }
}

Python

# Function to return the number of ways to
# form an array of size n such that sum of
# all elements is divisible by 2
def countWays(n, l, r):
    tL, tR = l, r
 
    # Represents first and last numbers
    # of each type (modulo 0 and 1)
    L, R = [0, 0], [0, 0]
    L[l % 2] = l
    R[r % 2] = r
 
    l += 1
    r -= 1
 
    if l <= tR and r >= tL:
        L[l % 2] = l
        R[r % 2] = r
 
    # Count of numbers of each type between range
    cnt0, cnt1 = 0, 0
    if R[0] and L[0]:
        cnt0 = (R[0] - L[0]) // 2 + 1
    if R[1] and L[1]:
        cnt1 = (R[1] - L[1]) // 2 + 1
 
    # Initialize variables for the first row
    prevRow0, prevRow1 = cnt0, cnt1
 
    # Iterate through the rows and update the previous row values
    for i in range(2, n+1):
        currRow0 = (cnt0 * prevRow0) + (cnt1 * prevRow1)
        currRow1 = (cnt0 * prevRow1) + (cnt1 * prevRow0)
        prevRow0 = currRow0
        prevRow1 = currRow1
 
    # Return the required count of ways
    return prevRow0
 
# Driver Code
if __name__ == '__main__':
    n, l, r = 2, 1, 3
    print(countWays(n, l, r))

C#

using System;
 
class GFG
{
    // Function to return the number of ways to
    // form an array of size n such that sum of
    // all elements is divisible by 2
    static int CountWays(int n, int l, int r)
    {
        int tL = l, tR = r;
 
        // Represents first and last numbers
        // of each type (modulo 0 and 1)
        int[] L = { 0, 0 };
        int[] R = { 0, 0 };
        L[l % 2] = l;
        R[r % 2] = r;
 
        l++;
        r--;
 
        if (l <= tR && r >= tL)
        {
            L[l % 2] = l;
            R[r % 2] = r;
        }
 
        // Count of numbers of each type between range
        int cnt0 = 0, cnt1 = 0;
        if (R[0] != 0 && L[0] != 0)
            cnt0 = (R[0] - L[0]) / 2 + 1;
        if (R[1] != 0 && L[1] != 0)
            cnt1 = (R[1] - L[1]) / 2 + 1;
 
        // Initialize variables for the first row
        int prevRow0 = cnt0, prevRow1 = cnt1;
 
        // Iterate through the rows and update the previous row values
        for (int i = 2; i <= n; i++)
        {
            int currRow0 = (cnt0 * prevRow0) + (cnt1 * prevRow1);
            int currRow1 = (cnt0 * prevRow1) + (cnt1 * prevRow0);
            prevRow0 = currRow0;
            prevRow1 = currRow1;
        }
 
        // Return the required count of ways
        return prevRow0;
    }
 
    // Driver Code
    static void Main(string[] args)
    {
        int n = 2, l = 1, r = 3;
        Console.WriteLine(CountWays(n, l, r));
 
        // Wait for key press to exit
        Console.ReadLine();
    }
}

Javascript

// Function to return the number of ways to
// form an array of size n such that sum of
// all elements is divisible by 2
function countWays(n, l, r) {
    let tL = l;
    let tR = r;
 
    // Represents first and last numbers of each type (modulo 0 and 1)
    let L = [0, 0];
    let R = [0, 0];
    L[l % 2] = l;
    R[r % 2] = r;
 
    l++;
    r--;
 
    if (l <= tR && r >= tL) {
        L[l % 2] = l;
        R[r % 2] = r;
    }
 
    // Count of numbers of each type between range
    let cnt0 = 0;
    let cnt1 = 0;
    if (R[0] !== 0 && L[0] !== 0)
        cnt0 = Math.floor((R[0] - L[0]) / 2) + 1;
    if (R[1] !== 0 && L[1] !== 0)
        cnt1 = Math.floor((R[1] - L[1]) / 2) + 1;
 
    // Initialize variables for the first row
    let prevRow0 = cnt0;
    let prevRow1 = cnt1;
 
    // Iterate through the rows and update the previous row values
    for (let i = 2; i <= n; i++) {
        let currRow0 = cnt0 * prevRow0 + cnt1 * prevRow1;
        let currRow1 = cnt0 * prevRow1 + cnt1 * prevRow0;
        prevRow0 = currRow0;
        prevRow1 = currRow1;
    }
 
    // Return the required count of ways
    return prevRow0;
}
 
// Driver Code
const n = 2;
const l = 1;
const r = 3;
console.log(countWays(n, l, r));

Output:

Time Complexity: O(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!

Ways to form an array having integers in given range such that total sum is divisible by 2

C++

Java

Python3

C#

Javascript

PHP

C++

Java

Python

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US