Recuento máximo de pares adyacentes con suma par en una array circular dada

Dada una array binaria circular arr[] de N enteros, la tarea es encontrar el recuento máximo de pares de elementos adyacentes cuya suma sea par donde cada elemento puede pertenecer a un par como máximo.

Ejemplo:

Entrada: arr[] = {1, 1, 1, 0, 1}
Salida: 2
Explicación: Se pueden formar dos pares de la siguiente manera: 

1. arr[0] y arr[4] forman el primer par, ya que la array dada es circular y arr[0] + arr[4] = 2.
2. arr[1] y arr[2] forman el segundo par.

Entrada: arr[] = {1, 1, 1, 0, 1, 1, 0, 0}
Salida: 3 

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . Se puede observar que los pares requeridos pueden estar formados por los mismos elementos solamente, es decir, (0, 0) o (1, 1) . Además, el número de pares que se pueden formar a partir de X 1 o 0 consecutivos es piso (X / 2). Por lo tanto, recorra la array dada y calcule todos los conjuntos posibles de enteros consecutivos y agregue X / 2 para cada conjunto en la respuesta.
Además, compruebe si tanto el 1 ^erconjunto y el último conjunto de enteros consecutivos tienen el mismo valor y el número de elementos en ambos conjuntos es impar, luego incremente la respuesta en 1.

A continuación se muestra la implementación del enfoque anterior:

//C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum count of
// pairs of adjacent elements with even
// sum in the given circular array
void findMaximumPairs(vector<int> arr)
{
   
    // Stores the value of current
    // integer during traversal
    int currentElement = arr[0], count = 1;
 
    // First chain's count and total number
    // of pairs is initially 0
    int firstChainCount = 0, totalPairs = 0;
 
    // flag is used to check if the current
    // chain is the first chain in array
    bool flag = true;
 
    for (int i = 1; i < arr.size(); i++)
    {
       
        // Count the number of
        // consecutive elements
        if (arr[i] == currentElement) {
            count++;
        }
        else {
 
            if (flag == true) {
 
                // Stores the count of
                // elements in 1st set
                firstChainCount = count;
                flag = false;
            }
 
            // Update answer
            totalPairs = totalPairs + count / 2;
 
            // Update current integer
            currentElement = arr[i];
            count = 1;
        }
    }
 
    totalPairs = totalPairs + count / 2;
    int lastChainCount = count;
 
    if (arr[0] == arr[arr.size() - 1]
        && firstChainCount % 2 == 1
        && lastChainCount % 2 == 1)
        totalPairs++;
 
    // Print Answer
    cout << (totalPairs);
}
 
// Driver Code
int main()
{
    vector<int> arr = { 1, 1, 1, 0, 1, 1, 0, 0 };
    findMaximumPairs(arr);
    return 0;
}
 
// This code is contributed by Potta Lokesh

// Java program for the above approach
import java.io.*;
 
class GFG {
    // Function to find maximum count of
    // pairs of adjacent elements with even
    // sum in the given circular array
    public static void findMaximumPairs(int[] arr)
    {
        // Stores the value of current
        // integer during traversal
        int currentElement = arr[0], count = 1;
 
        // First chain's count and total number
        // of pairs is initially 0
        int firstChainCount = 0, totalPairs = 0;
 
        // flag is used to check if the current
        // chain is the first chain in array
        boolean flag = true;
 
        for (int i = 1; i < arr.length; i++) {
            // Count the number of
            // consecutive elements
            if (arr[i] == currentElement) {
                count++;
            }
            else {
 
                if (flag == true) {
 
                    // Stores the count of
                    // elements in 1st set
                    firstChainCount = count;
                    flag = false;
                }
 
                // Update answer
                totalPairs = totalPairs + count / 2;
 
                // Update current integer
                currentElement = arr[i];
                count = 1;
            }
        }
 
        totalPairs = totalPairs + count / 2;
        int lastChainCount = count;
 
        if (arr[0] == arr[arr.length - 1]
            && firstChainCount % 2 == 1
            && lastChainCount % 2 == 1)
            totalPairs++;
 
        // Print Answer
        System.out.println(totalPairs);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 1, 1, 0, 1, 1, 0, 0 };
        findMaximumPairs(arr);
    }
}

# Python program for the above approach
import math
 
# Function to find maximum count of
# pairs of adjacent elements with even
# sum in the given circular array
def findMaximumPairs(arr):
   
    # Stores the value of current
    # integer during traversal
    currentElement = arr[0]
    count = 1
 
    # First chain's count and total number
    # of pairs is initially 0
    firstChainCount = 0
    totalPairs = 0
 
    # flag is used to check if the current
    # chain is the first chain in array
    flag = True;
 
    for i in range(1, len(arr)):
       
        # Count the number of
        # consecutive elements
        if (arr[i] == currentElement):
            count = count + 1
             
        else:
            if (flag == True):
 
                # Stores the count of
                # elements in 1st set
                firstChainCount = count
                flag = False
 
            # Update answer
            totalPairs = totalPairs + math.floor(count / 2)
 
            # Update current integer
            currentElement = arr[i]
            count = 1
 
    totalPairs = totalPairs + math.floor(count / 2)
    lastChainCount = count
 
    if (arr[0] == arr[len(arr) - 1]
        and firstChainCount % 2 == 1
        and lastChainCount % 2 == 1):
        totalPairs = totalPairs + 1
 
    # Print Answer
    print(totalPairs)
 
# Driver Code
arr = [ 1, 1, 1, 0, 1, 1, 0, 0 ]
findMaximumPairs(arr)
 
# This code is contributed by Samim Hossain Mondal.

// C# code to implement above approach
using System;
class GFG {
     
    // Function to find maximum count of
    // pairs of adjacent elements with even
    // sum in the given circular array
    static void findMaximumPairs(int[] arr)
    {
        // Stores the value of current
        // integer during traversal
        int currentElement = arr[0], count = 1;
 
        // First chain's count and total number
        // of pairs is initially 0
        int firstChainCount = 0, totalPairs = 0;
 
        // flag is used to check if the current
        // chain is the first chain in array
        bool flag = true;
 
        for (int i = 1; i < arr.Length; i++) {
            // Count the number of
            // consecutive elements
            if (arr[i] == currentElement) {
                count++;
            }
            else {
 
                if (flag == true) {
 
                    // Stores the count of
                    // elements in 1st set
                    firstChainCount = count;
                    flag = false;
                }
 
                // Update answer
                totalPairs = totalPairs + count / 2;
 
                // Update current integer
                currentElement = arr[i];
                count = 1;
            }
        }
 
        totalPairs = totalPairs + count / 2;
        int lastChainCount = count;
 
        if (arr[0] == arr[arr.Length - 1]
            && firstChainCount % 2 == 1
            && lastChainCount % 2 == 1)
            totalPairs++;
 
        // Print Answer
        Console.Write(totalPairs);
    }
 
    // Driver Code
    public static void Main()
    {
        int []arr = { 1, 1, 1, 0, 1, 1, 0, 0 };
        findMaximumPairs(arr);
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript program for the above approach
 
// Function to find maximum count of
// pairs of adjacent elements with even
// sum in the given circular array
const findMaximumPairs = (arr) => {
     
    // Stores the value of current
    // integer during traversal
    let currentElement = arr[0], count = 1;
 
    // First chain's count and total number
    // of pairs is initially 0
    let firstChainCount = 0, totalPairs = 0;
 
    // flag is used to check if the current
    // chain is the first chain in array
    let flag = true;
 
    for(let i = 1; i < arr.length; i++)
    {
         
        // Count the number of
        // consecutive elements
        if (arr[i] == currentElement)
        {
            count++;
        }
        else
        {
            if (flag == true)
            {
                 
                // Stores the count of
                // elements in 1st set
                firstChainCount = count;
                flag = false;
            }
 
            // Update answer
            totalPairs = totalPairs + parseInt(count / 2);
 
            // Update current integer
            currentElement = arr[i];
            count = 1;
        }
    }
 
    totalPairs = totalPairs + parseInt(count / 2);
    let lastChainCount = count;
 
    if (arr[0] == arr[arr.length - 1] &&
            firstChainCount % 2 == 1 &&
             lastChainCount % 2 == 1)
        totalPairs++;
 
    // Print Answer
    document.write(totalPairs);
}
 
// Driver Code
let arr = [ 1, 1, 1, 0, 1, 1, 0, 0 ];
 
findMaximumPairs(arr);
 
// This code is contributed by rakeshsahni
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)