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 ith 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 ith 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 2int 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 Codeint main(){ int n = 2, l = 1, r = 3; cout << countWays(n, l, r); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the number of ways to// form an array of size n such that sum of// all elements is divisible by 2static 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 Codepublic 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 2def 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 Coden, l, r = 2, 1, 3print(countWays(n, l, r))# This code is contributed # by Mohit Kumar |
C#
// C# implementation of the approachusing 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 2static 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 Codestatic 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
5
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 2int 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 Codeint 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 2def 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 Codeif __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 2function 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 Codeconst n = 2;const l = 1;const r = 3;console.log(countWays(n, l, r)); |
Output:
5
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
