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

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: 

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:

Output: 

5

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