Posted on by Kalkicode
Code Dynamic Programming

# Count subarrays with same even and odd elements

In this article, we will explore the problem of counting subarrays that have the same number of even and odd elements. We'll discuss an efficient solution using dynamic programming, along with a detailed explanation of the provided C code. The article aims to provide a comprehensive understanding of the problem and its solution.

Subarrays are contiguous subsets of an array. Counting the number of subarrays with specific properties is a common problem in computer science and algorithmic competitions. In this article, we'll focus on counting subarrays that contain an equal number of even and odd elements. We'll present an efficient solution using dynamic programming and analyze a provided C code implementation.

## Problem Statement:

Given an array of integers, we are required to count the number of subarrays that have the same number of even and odd elements. For example, in the array [2, 3, 2, 3], there are four subarrays with an equal number of even and odd elements: [2, 3], [2, 3], [2, 3, 2], and [3, 2].

## Code solution:

``````// C Program
// Count subarrays with same even and odd elements
#include <stdio.h>

void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
void countSameEvenOdd(int arr[], int n)
{
int count = 0;
int result = 0;
int dp[n][2];
// Set intial value
for (int i = 0; i < n; ++i)
{
dp[i][0] = 0;
dp[i][1] = 0;
}
dp[0][0] = 1;
for (int i = 0; i < n; ++i)
{
if (arr[i] % 2 == 0)
{
// When element is even
count++;
}
else
{
// When element is odd
count--;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count][1];
// Increase frequency
dp[-count][1] += 1;
}
else
{
// Even Number is greater
result += dp[count][0];
// Increase frequency
dp[count][0] += 1;
}
}
printArr(arr, n);
// Display calculated result
printf(" Result : %d \n", result);
}
int main()
{
int a[] = {
2 , 3 , 2 , 3
};
int b[] = {
1 , 1 , 1 , 2 , 2 , 2 , 7
};
int c[] = {
7 , 2 , 2 , 1
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
countSameEvenOdd(a, l1);
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
countSameEvenOdd(b, l2);
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
countSameEvenOdd(c, l3);
return 0;
}``````

#### Output

``````  2  3  2  3
Result : 4
1  1  1  2  2  2  7
Result : 5
7  2  2  1
Result : 3``````
``````// Java program for
// Count subarrays with same even and odd elements
public class Subarrays
{
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
public void countSameEvenOdd(int[] arr, int n)
{
int count = 0;
int result = 0;
int[][] dp = new int[n][2];
// Set intial value
for (int i = 0; i < n; ++i)
{
dp[i][0] = 0;
dp[i][1] = 0;
}
dp[0][0] = 1;
for (int i = 0; i < n; ++i)
{
if (arr[i] % 2 == 0)
{
// When element is even
count++;
}
else
{
// When element is odd
count--;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count][1];
// Increase frequency
dp[-count][1] += 1;
}
else
{
// Even Number is greater
result += dp[count][0];
// Increase frequency
dp[count][0] += 1;
}
}
printArr(arr, n);
// Display calculated result
System.out.println(" Result : " + result);
}
public static void main(String[] args)
{
// Array of integer elements
int[] a = {
2 , 3 , 2 , 3
};
int[] b = {
1 , 1 , 1 , 2 , 2 , 2 , 7
};
int[] c = {
7 , 2 , 2 , 1
};
// Get the size
int l1 = a.length;
int l2 = b.length;
int l3 = c.length;
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}
}``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Count subarrays with same even and odd elements
class Subarrays
{
public: void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
void countSameEvenOdd(int arr[], int n)
{
int count = 0;
int result = 0;
int dp[n][2];
// Set intial value
for (int i = 0; i < n; ++i)
{
dp[i][0] = 0;
dp[i][1] = 0;
}
dp[0][0] = 1;
for (int i = 0; i < n; ++i)
{
if (arr[i] % 2 == 0)
{
// When element is even
count++;
}
else
{
// When element is odd
count--;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count][1];
// Increase frequency
dp[-count][1] += 1;
}
else
{
// Even Number is greater
result += dp[count][0];
// Increase frequency
dp[count][0] += 1;
}
}
this->printArr(arr, n);
// Display calculated result
cout << " Result : " << result << endl;
}
};
int main()
{
// Array of integer elements
int a[] = {
2 , 3 , 2 , 3
};
int b[] = {
1 , 1 , 1 , 2 , 2 , 2 , 7
};
int c[] = {
7 , 2 , 2 , 1
};
// Get the size
int l1 = sizeof(a) / sizeof(a[0]);
int l2 = sizeof(b) / sizeof(b[0]);
int l3 = sizeof(c) / sizeof(c[0]);
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
return 0;
}``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````// Include namespace system
using System;
// Csharp program for
// Count subarrays with same even and odd elements
public class Subarrays
{
public void printArr(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public void countSameEvenOdd(int[] arr, int n)
{
int count = 0;
int result = 0;
int[,] dp = new int[n,2];
// Set intial value
for (int i = 0; i < n; ++i)
{
dp[i,0] = 0;
dp[i,1] = 0;
}
dp[0,0] = 1;
for (int i = 0; i < n; ++i)
{
if (arr[i] % 2 == 0)
{
// When element is even
count++;
}
else
{
// When element is odd
count--;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count,1];
// Increase frequency
dp[-count,1] += 1;
}
else
{
// Even Number is greater
result += dp[count,0];
// Increase frequency
dp[count,0] += 1;
}
}
this.printArr(arr, n);
// Display calculated result
Console.WriteLine(" Result : " + result);
}
public static void Main(String[] args)
{
// Array of integer elements
int[] a = {
2 , 3 , 2 , 3
};
int[] b = {
1 , 1 , 1 , 2 , 2 , 2 , 7
};
int[] c = {
7 , 2 , 2 , 1
};
// Get the size
int l1 = a.Length;
int l2 = b.Length;
int l3 = c.Length;
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}
}``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````package main
import "fmt"
// Go program for
// Count subarrays with same even and odd elements
type Subarrays struct {}
func getSubarrays() * Subarrays {
var me *Subarrays = &Subarrays {}
return me
}
func(this Subarrays) printArr(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func(this Subarrays) countSameEvenOdd(arr[] int, n int) {
var count int = 0
var result int = 0
var dp = make([][] int, n)
for i := 0; i < n; i++{
dp[i] = make([]int,2)
}
// Set intial value
for i := 0 ; i < n ; i++ {
dp[i][0] = 0
dp[i][1] = 0
}
dp[0][0] = 1
for i := 0 ; i < n ; i++ {
if arr[i] % 2 == 0 {
// When element is even
count++
} else {
// When element is odd
count--
}
if count < 0 {
// Odd Number is greater
result += dp[-count][1]
// Increase frequency
dp[-count][1] += 1
} else {
// Even Number is greater
result += dp[count][0]
// Increase frequency
dp[count][0] += 1
}
}
this.printArr(arr, n)
// Display calculated result
fmt.Println(" Result : ", result)
}
func main() {
var task * Subarrays = getSubarrays()
// Array of integer elements
var a = [] int {
2,
3,
2,
3,
}
var b = [] int {
1,
1,
1,
2,
2,
2,
7,
}
var c = [] int {
7,
2,
2,
1,
}
// Get the size
var l1 int = len(a)
var l2 int = len(b)
var l3 int = len(c)
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````<?php
// Php program for
// Count subarrays with same even and odd elements
class Subarrays
{
public	function printArr(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
echo("\n");
}
public	function countSameEvenOdd(\$arr, \$n)
{
\$count = 0;
\$result = 0;
\$dp = array_fill(0, \$n, array_fill(0, 2, 0));
\$dp[0][0] = 1;
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$arr[\$i] % 2 == 0)
{
// When element is even
\$count++;
}
else
{
// When element is odd
\$count--;
}
if (\$count < 0)
{
// Odd Number is greater
\$result += \$dp[-\$count][1];
// Increase frequency
\$dp[-\$count][1] += 1;
}
else
{
// Even Number is greater
\$result += \$dp[\$count][0];
// Increase frequency
\$dp[\$count][0] += 1;
}
}
\$this->printArr(\$arr, \$n);
// Display calculated result
echo(" Result : ".\$result.
"\n");
}
}

function main()
{
// Array of integer elements
\$a = array(2, 3, 2, 3);
\$b = array(1, 1, 1, 2, 2, 2, 7);
\$c = array(7, 2, 2, 1);
// Get the size
\$l1 = count(\$a);
\$l2 = count(\$b);
\$l3 = count(\$c);
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}
main();``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````// Node JS program for
// Count subarrays with same even and odd elements
class Subarrays
{
printArr(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
countSameEvenOdd(arr, n)
{
var count = 0;
var result = 0;
var dp = Array(n).fill(0).map(() => new Array(2).fill(0));
dp[0][0] = 1;
for (var i = 0; i < n; ++i)
{
if (arr[i] % 2 == 0)
{
// When element is even
count++;
}
else
{
// When element is odd
count--;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count][1];
// Increase frequency
dp[-count][1] += 1;
}
else
{
// Even Number is greater
result += dp[count][0];
// Increase frequency
dp[count][0] += 1;
}
}
this.printArr(arr, n);
// Display calculated result
console.log(" Result : " + result);
}
}

function main()
{
// Array of integer elements
var a = [2, 3, 2, 3];
var b = [1, 1, 1, 2, 2, 2, 7];
var c = [7, 2, 2, 1];
// Get the size
var l1 = a.length;
var l2 = b.length;
var l3 = c.length;
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}
main();``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````#  Python 3 program for
#  Count subarrays with same even and odd elements
class Subarrays :
def printArr(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

print(end = "\n")

def countSameEvenOdd(self, arr, n) :
count = 0
result = 0
dp = [[0] * (2) for _ in range(n) ]
dp[0][0] = 1
i = 0
while (i < n) :
if (arr[i] % 2 == 0) :
#  When element is even
count += 1
else :
#  When element is odd
count -= 1

if (count < 0) :
#  Odd Number is greater
result += dp[-count][1]
#  Increase frequency
dp[-count][1] += 1
else :
#  Even Number is greater
result += dp[count][0]
#  Increase frequency
dp[count][0] += 1

i += 1

self.printArr(arr, n)
#  Display calculated result
print(" Result : ", result)

def main() :
#  Array of integer elements
a = [2, 3, 2, 3]
b = [1, 1, 1, 2, 2, 2, 7]
c = [7, 2, 2, 1]
#  Get the size
l1 = len(a)
l2 = len(b)
l3 = len(c)
#  Test A
#  arr = [2, 3, 2,3]
#  --------------------------
#   ➀  [2, 3, 2,3]
#   ➁        [2,3]
#   ➂  [2, 3]
#   ➃     [3, 2]
#  ---------------
#   Total : 4
#  Test B
#  arr = [1,1,1,2,2,2,7]
#  --------------------------
#   ➀  [1,1,1,2,2,2]
#   ➁      [1,2]
#   ➂    [1,1,2,2]
#   ➃              [2,7]
#   ➄      [1,1,2,2,2,7]
#  ---------------
#   Total : 5
#  Test C
#  arr = [7, 2, 2, 1]
#  --------------------------
#   ➀  [7, 2]
#   ➁           [2,1]
#   ➂  [7, 2, 2, 1]
#  ---------------
#   Total : 3

if __name__ == "__main__": main()``````

#### Output

``````  2  3  2  3
Result :  4
1  1  1  2  2  2  7
Result :  5
7  2  2  1
Result :  3``````
``````#  Ruby program for
#  Count subarrays with same even and odd elements
class Subarrays
def printArr(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

print("\n")
end

def countSameEvenOdd(arr, n)
count = 0
result = 0
dp = Array.new(n) {Array.new(2) {0}}
dp[0][0] = 1
i = 0
while (i < n)
if (arr[i] % 2 == 0)
#  When element is even
count += 1
else

#  When element is odd
count -= 1
end

if (count < 0)
#  Odd Number is greater
result += dp[-count][1]
#  Increase frequency
dp[-count][1] += 1
else

#  Even Number is greater
result += dp[count][0]
#  Increase frequency
dp[count][0] += 1
end

i += 1
end

self.printArr(arr, n)
#  Display calculated result
print(" Result : ", result, "\n")
end

end

def main()
#  Array of integer elements
a = [2, 3, 2, 3]
b = [1, 1, 1, 2, 2, 2, 7]
c = [7, 2, 2, 1]
#  Get the size
l1 = a.length
l2 = b.length
l3 = c.length
#  Test A
#  arr = [2, 3, 2,3]
#  --------------------------
#   ➀  [2, 3, 2,3]
#   ➁        [2,3]
#   ➂  [2, 3]
#   ➃     [3, 2]
#  ---------------
#   Total : 4
#  Test B
#  arr = [1,1,1,2,2,2,7]
#  --------------------------
#   ➀  [1,1,1,2,2,2]
#   ➁      [1,2]
#   ➂    [1,1,2,2]
#   ➃              [2,7]
#   ➄      [1,1,2,2,2,7]
#  ---------------
#   Total : 5
#  Test C
#  arr = [7, 2, 2, 1]
#  --------------------------
#   ➀  [7, 2]
#   ➁           [2,1]
#   ➂  [7, 2, 2, 1]
#  ---------------
#   Total : 3
end

main()``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3
``````
``````// Scala program for
// Count subarrays with same even and odd elements
class Subarrays()
{
def printArr(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
def countSameEvenOdd(arr: Array[Int], n: Int): Unit = {
var count: Int = 0;
var result: Int = 0;
var dp: Array[Array[Int]] = Array.fill[Int](n, 2)(0);
dp(0)(0) = 1;
var i: Int = 0;
while (i < n)
{
if (arr(i) % 2 == 0)
{
// When element is even
count += 1;
}
else
{
// When element is odd
count -= 1;
}
if (count < 0)
{
// Odd Number is greater
result += dp(-count)(1);
// Increase frequency
dp(-count)(1) += 1;
}
else
{
// Even Number is greater
result += dp(count)(0);
// Increase frequency
dp(count)(0) += 1;
}
i += 1;
}
printArr(arr, n);
// Display calculated result
println(" Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarrays = new Subarrays();
// Array of integer elements
var a: Array[Int] = Array(2, 3, 2, 3);
var b: Array[Int] = Array(1, 1, 1, 2, 2, 2, 7);
var c: Array[Int] = Array(7, 2, 2, 1);
// Get the size
var l1: Int = a.length;
var l2: Int = b.length;
var l3: Int = c.length;
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}
}``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````
``````import Foundation;
// Swift 4 program for
// Count subarrays with same even and odd elements
class Subarrays
{
func printArr(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func countSameEvenOdd(_ arr: [Int], _ n: Int)
{
var count: Int = 0;
var result: Int = 0;
var dp: [
[Int]
] = Array(repeating: Array(repeating: 0, count: 2), count: n);
dp[0][0] = 1;
var i: Int = 0;
while (i < n)
{
if (arr[i] % 2 == 0)
{
// When element is even
count += 1;
}
else
{
// When element is odd
count -= 1;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count][1];
// Increase frequency
dp[-count][1] += 1;
}
else
{
// Even Number is greater
result += dp[count][0];
// Increase frequency
dp[count][0] += 1;
}
i += 1;
}
self.printArr(arr, n);
// Display calculated result
print(" Result : ", result);
}
}
func main()
{
// Array of integer elements
let a: [Int] = [2, 3, 2, 3];
let b: [Int] = [1, 1, 1, 2, 2, 2, 7];
let c: [Int] = [7, 2, 2, 1];
// Get the size
let l1: Int = a.count;
let l2: Int = b.count;
let l3: Int = c.count;
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}
main();``````

#### Output

``````  2  3  2  3
Result :  4
1  1  1  2  2  2  7
Result :  5
7  2  2  1
Result :  3``````
``````// Kotlin program for
// Count subarrays with same even and odd elements
class Subarrays
{
fun printArr(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
fun countSameEvenOdd(arr: Array < Int > , n: Int): Unit
{
var count: Int = 0;
var result: Int = 0;
val dp: Array < Array < Int >> = Array(n)
{
Array(2)
{
0
}
};
dp[0][0] = 1;
var i: Int = 0;
while (i < n)
{
if (arr[i] % 2 == 0)
{
// When element is even
count += 1;
}
else
{
// When element is odd
count -= 1;
}
if (count < 0)
{
// Odd Number is greater
result += dp[-count][1];
// Increase frequency
dp[-count][1] += 1;
}
else
{
// Even Number is greater
result += dp[count][0];
// Increase frequency
dp[count][0] += 1;
}
i += 1;
}
this.printArr(arr, n);
// Display calculated result
println(" Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
// Array of integer elements
val a: Array < Int > = arrayOf(2, 3, 2, 3);
val b: Array < Int > = arrayOf(1, 1, 1, 2, 2, 2, 7);
val c: Array < Int > = arrayOf(7, 2, 2, 1);
// Get the size
val l1: Int = a.count();
val l2: Int = b.count();
val l3: Int = c.count();
// Test A
// arr = [2, 3, 2,3]
// --------------------------
//
//  ➀  [2, 3, 2,3]
//  ➁        [2,3]
//  ➂  [2, 3]
//  ➃     [3, 2]
// ---------------
//  Total : 4
// Test B
// arr = [1,1,1,2,2,2,7]
// --------------------------
//  ➀  [1,1,1,2,2,2]
//  ➁      [1,2]
//  ➂    [1,1,2,2]
//  ➃              [2,7]
//  ➄      [1,1,2,2,2,7]
// ---------------
//  Total : 5
// Test C
// arr = [7, 2, 2, 1]
// --------------------------
//  ➀  [7, 2]
//  ➁           [2,1]
//  ➂  [7, 2, 2, 1]
// ---------------
//  Total : 3
}``````

#### Output

`````` 2 3 2 3
Result : 4
1 1 1 2 2 2 7
Result : 5
7 2 2 1
Result : 3``````

## Solution:

The provided C code presents an efficient solution to the problem using dynamic programming. Let's analyze the code step by step.

1. The code begins by defining a function named "countSameEvenOdd," which takes an array and its length as input.

2. Inside the function, a 2D array called "dp" is initialized. This array will be used for dynamic programming calculations. It has dimensions of [n][2], where n represents the length of the input array, and 2 represents two states: even and odd.

3. The code sets the initial values of the "dp" array to zero.

4. The variable "count" is initialized to zero. It will keep track of the difference between the counts of even and odd elements encountered in the array.

5. The variable "result" is initialized to zero. It will store the final count of subarrays with an equal number of even and odd elements.

6. The code iterates over each element in the array.

7. If the current element is even (arr[i] % 2 == 0), the "count" variable is incremented.

8. If the current element is odd, the "count" variable is decremented.

9. If the "count" variable becomes negative, it means that the number of odd elements encountered so far is greater than the number of even elements. In this case, the code adds the value of dp[-count][1] to the "result" variable. This value represents the count of subarrays with an equal number of even and odd elements ending at the current index.

10. The frequency of the encountered count (-count) is increased by 1 in dp[-count][1].

11. If the "count" variable is positive or zero, it means that the number of even elements encountered so far is greater than or equal to the number of odd elements. In this case, the code adds the value of dp[count][0] to the "result" variable. This value represents the count of subarrays with an equal number of even and odd elements ending at the current index.

12. The frequency of the encountered count (count) is increased by 1 in dp[count][0].

13. After iterating through all the elements, the function prints the input array using the "printArr" function.

14. Finally, the function displays the calculated result.

15. The main function demonstrates the usage of the "countSameEvenOdd" function on three test cases: arrays [2, 3, 2, 3], [1, 1, 1, 2, 2, 2, 7], and [7, 2, 2, 1].

16. The size of each array is calculated using the "sizeof" operator and division by the size of a single element.

17. The "countSameEvenOdd" function is called for each test case, and the results are printed.

Counting subarrays with an equal number of even and odd elements is an interesting problem that can be efficiently solved using dynamic programming techniques. The provided C code demonstrates an implementation of the solution. We've discussed the code in detail, explaining each step and the underlying logic. Understanding this solution will help in solving similar problems and enhance your programming skills.

Remember to analyze the complexity of the algorithm, which in this case is O(n), where n is the length of the input array. This linear complexity makes the solution efficient and suitable for large inputs.

By applying the concepts and techniques discussed in this article, you'll be well-prepared to tackle similar problems and develop effective solutions.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post