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)
    {
        Subarrays task = new Subarrays();
        // 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
        task.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
        task.countSameEvenOdd(b, l2);
        // Test C
        // arr = [7, 2, 2, 1]
        // --------------------------
        //  ➀  [7, 2]
        //  ➁           [2,1]
        //  ➂  [7, 2, 2, 1]
        // ---------------
        //  Total : 3
        task.countSameEvenOdd(c, l3);
    }
}

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()
{
    Subarrays *task = new Subarrays();
    // 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
    task->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
    task->countSameEvenOdd(b, l2);
    // Test C
    // arr = [7, 2, 2, 1]
    // --------------------------
    //  ➀  [7, 2]
    //  ➁           [2,1]
    //  ➂  [7, 2, 2, 1]
    // ---------------
    //  Total : 3
    task->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
// 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)
    {
        Subarrays task = new Subarrays();
        // 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
        task.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
        task.countSameEvenOdd(b, l2);
        // Test C
        // arr = [7, 2, 2, 1]
        // --------------------------
        //  ➀  [7, 2]
        //  ➁           [2,1]
        //  ➂  [7, 2, 2, 1]
        // ---------------
        //  Total : 3
        task.countSameEvenOdd(c, l3);
    }
}

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
    task.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
    task.countSameEvenOdd(b, l2)
    // Test C
    // arr = [7, 2, 2, 1]
    // --------------------------
    //  ➀  [7, 2]
    //  ➁           [2,1]
    //  ➂  [7, 2, 2, 1]
    // ---------------
    //  Total : 3
    task.countSameEvenOdd(c, l3)
}

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()
{
    $task = new Subarrays();
    // 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
    $task->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
    $task->countSameEvenOdd($b, $l2);
    // Test C
    // arr = [7, 2, 2, 1]
    // --------------------------
    //  ➀  [7, 2]
    //  ➁           [2,1]
    //  ➂  [7, 2, 2, 1]
    // ---------------
    //  Total : 3
    $task->countSameEvenOdd($c, $l3);
}
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()
{
    var task = new Subarrays();
    // 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
    task.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
    task.countSameEvenOdd(b, l2);
    // Test C
    // arr = [7, 2, 2, 1]
    // --------------------------
    //  ➀  [7, 2]
    //  ➁           [2,1]
    //  ➂  [7, 2, 2, 1]
    // ---------------
    //  Total : 3
    task.countSameEvenOdd(c, l3);
}
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() :
    task = Subarrays()
    #  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
    task.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
    task.countSameEvenOdd(b, l2)
    #  Test C
    #  arr = [7, 2, 2, 1]
    #  --------------------------
    #   ➀  [7, 2]
    #   ➁           [2,1]
    #   ➂  [7, 2, 2, 1]
    #  ---------------
    #   Total : 3
    task.countSameEvenOdd(c, l3)

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() 
    task = Subarrays.new()
    #  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
    task.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
    task.countSameEvenOdd(b, l2)
    #  Test C
    #  arr = [7, 2, 2, 1]
    #  --------------------------
    #   ➀  [7, 2]
    #   ➁           [2,1]
    #   ➂  [7, 2, 2, 1]
    #  ---------------
    #   Total : 3
    task.countSameEvenOdd(c, l3)
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
        task.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
        task.countSameEvenOdd(b, l2);
        // Test C
        // arr = [7, 2, 2, 1]
        // --------------------------
        //  ➀  [7, 2]
        //  ➁           [2,1]
        //  ➂  [7, 2, 2, 1]
        // ---------------
        //  Total : 3
        task.countSameEvenOdd(c, l3);
    }
}

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()
{
    let task: Subarrays = Subarrays();
    // 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
    task.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
    task.countSameEvenOdd(b, l2);
    // Test C
    // arr = [7, 2, 2, 1]
    // --------------------------
    //  ➀  [7, 2]
    //  ➁           [2,1]
    //  ➂  [7, 2, 2, 1]
    // ---------------
    //  Total : 3
    task.countSameEvenOdd(c, l3);
}
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
{
    val task: Subarrays = Subarrays();
    // 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
    task.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
    task.countSameEvenOdd(b, l2);
    // Test C
    // arr = [7, 2, 2, 1]
    // --------------------------
    //  ➀  [7, 2]
    //  ➁           [2,1]
    //  ➂  [7, 2, 2, 1]
    // ---------------
    //  Total : 3
    task.countSameEvenOdd(c, l3);
}

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.

New Comment