Dada una array arr[] de tamaño N , que tiene el mismo número de enteros pares e impares , la tarea es encontrar la cantidad mínima de subarreglos necesarios para invertir para que la suma de pares de elementos adyacentes sea impar.
Ejemplos:
Entrada: arr[] = {13, 2, 6, 8, 3, 5, 7, 10, 14, 15}
Salida: 3
Explicación:
Paso 1: Invierta el subarreglo [2, 4] para modificar el arreglo a {13, 2, 3, 8, 6, 5, 7, 10, 14, 15}
Paso 2: invertir el subarreglo [4, 5] para modificar el arreglo a {13, 2, 3, 8, 5, 6, 7, 10, 14, 15}
Paso 3: Invierta el subarreglo [8, 9] para modificar el arreglo a {13, 2, 3, 8, 5, 6, 7, 10, 15, 14}
Después de las inversiones anteriores, la suma de todos los adyacentes los pares de elementos son impares.
Por lo tanto, las reversiones mínimas requeridas son 3.Entrada: arr[] = {1, 3, 4, 5, 9, 6, 8}
Salida: 2
Enfoque: Para que la suma de los elementos adyacentes sea impar, la idea es ordenar los elementos de manera par-impar o par-impar. Para minimizar el recuento de operaciones de inversión, observe la siguiente propiedad de la array dada:
- Si hay un subarreglo de longitud M que tiene todos los elementos de la misma paridad, entonces también existe un subarreglo de longitud M que tiene todos los elementos de la paridad opuesta, ya que el recuento de elementos pares e impares es el mismo en el arreglo.
- Por lo tanto, el conteo de la operación de inversión requerida para hacer el subarreglo de longitud M de paridad alterna es (M – 1) .
Siga los pasos a continuación para resolver el problema:
- Recorra la array dada y encuentre el recuento de inversión de subarreglo requerido para cada uno de los mismos elementos pares e impares consecutivos en la array.
- Sea cntOdd y cntEven respectivamente el recuento de inversión para elementos pares e impares consecutivos .
- El recuento mínimo de reversión viene dado por el máximo de cntOdd y cntEven , ya que la tarea es eliminar todos los mismos elementos consecutivos y el máximo de elementos consecutivos necesarios para eliminar.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count reversals to
// separate elements with same parity
int separate(int arr[], int n, int parity)
{
int count = 1, res = 0;
// Traverse the given array
for (int i = 1; i < n; i++) {
// Count size of subarray having
// integers with same parity only
if (((arr[i] + parity) & 1)
&& ((arr[i - 1] + parity) & 1))
count++;
// Otherwise
else {
// Reversals required is equal
// to one less than subarray size
if (count > 1)
res += count - 1;
count = 1;
}
}
// Return the total reversals
return res;
}
// Function to print the array elements
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Function to count the minimum reversals
// required to make sum
// of all adjacent elements odd
void requiredOps(int arr[], int N)
{
// Stores operations required for
// separating adjacent odd elements
int res1 = separate(arr, N, 0);
// Stores operations required for
// separating adjacent even elements
int res2 = separate(arr, N, 1);
// Maximum of two is the return
cout << max(res1, res2);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 13, 2, 6, 8, 3, 5,
7, 10, 14, 15 };
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
requiredOps(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count reversals to
// separate elements with same parity
static int separate(int arr[], int n,
int parity)
{
int count = 1, res = 0;
// Traverse the given array
for(int i = 1; i < n; i++)
{
// Count size of subarray having
// integers with same parity only
if (((arr[i] + parity) & 1) != 0 &&
((arr[i - 1] + parity) & 1) != 0)
count++;
// Otherwise
else
{
// Reversals required is equal
// to one less than subarray size
if (count > 1)
res += count - 1;
count = 1;
}
}
// Return the total reversals
return res;
}
// Function to print the array elements
void printArray(int arr[], int n)
{
for(int i = 0; i < n; i++)
System.out.println(arr[i] + " ");
}
// Function to count the minimum reversals
// required to make sum
// of all adjacent elements odd
static void requiredOps(int arr[], int N)
{
// Stores operations required for
// separating adjacent odd elements
int res1 = separate(arr, N, 0);
// Stores operations required for
// separating adjacent even elements
int res2 = separate(arr, N, 1);
// Maximum of two is the return
System.out.print(Math.max(res1, res2));
}
// Driver Code
public static void main(String args[])
{
// Given array arr[]
int arr[] = { 13, 2, 6, 8, 3, 5,
7, 10, 14, 15 };
// Size of array
int N = arr.length;
// Function Call
requiredOps(arr, N);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the # above approach # Function to count reversals # to separate elements with # same parity def separate(arr, n, parity): count = 1 res = 0 # Traverse the given array for i in range(1, n): # Count size of subarray # having integers with # same parity only if (((arr[i] + parity) & 1) and ((arr[i - 1] + parity) & 1)): count += 1 # Otherwise else: # Reversals required is # equal to one less than # subarray size if (count > 1): res += count - 1 count = 1 # Return the total # reversals return res # Function to print the # array elements def printArray(arr, n): for i in range(n): print(arr[i], end = " ") # Function to count the minimum # reversals required to make # make sum of all adjacent # elements odd def requiredOps(arr, N): # Stores operations required # for separating adjacent # odd elements res1 = separate(arr, N, 0) # Stores operations required # for separating adjacent # even elements res2 = separate(arr, N, 1) # Maximum of two is the # return print(max(res1, res2)) # Driver Code if __name__ == "__main__": # Given array arr[] arr = [13, 2, 6, 8, 3, 5, 7, 10, 14, 15] # Size of array N = len(arr) # Function Call requiredOps(arr, N) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to count reversals to
// separate elements with same parity
static int separate(int[] arr, int n,
int parity)
{
int count = 1, res = 0;
// Traverse the given array
for(int i = 1; i < n; i++)
{
// Count size of subarray having
// integers with same parity only
if (((arr[i] + parity) & 1) != 0 &&
((arr[i - 1] + parity) & 1) != 0)
count++;
// Otherwise
else
{
// Reversals required is equal
// to one less than subarray size
if (count > 1)
res += count - 1;
count = 1;
}
}
// Return the total reversals
return res;
}
// Function to print the array elements
void printArray(int[] arr, int n)
{
for(int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Function to count the minimum reversals
// required to make make sum
// of all adjacent elements odd
static void requiredOps(int[] arr, int N)
{
// Stores operations required for
// separating adjacent odd elements
int res1 = separate(arr, N, 0);
// Stores operations required for
// separating adjacent even elements
int res2 = separate(arr, N, 1);
// Maximum of two is the return
Console.Write(Math.Max(res1, res2));
}
// Driver code
public static void Main()
{
// Given array arr[]
int[] arr = { 13, 2, 6, 8, 3, 5,
7, 10, 14, 15 };
// Size of array
int N = arr.Length;
// Function Call
requiredOps(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count reversals to
// separate elements with same parity
function separate(arr, n, parity)
{
let count = 1, res = 0;
// Traverse the given array
for(let i = 1; i < n; i++)
{
// Count size of subarray having
// integers with same parity only
if (((arr[i] + parity) & 1) != 0 &&
((arr[i - 1] + parity) & 1) != 0)
count++;
// Otherwise
else
{
// Reversals required is equal
// to one less than subarray size
if (count > 1)
res += count - 1;
count = 1;
}
}
// Return the total reversals
return res;
}
// Function to print the array elements
function printArray(arr, n)
{
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Function to count the minimum reversals
// required to make make sum
// of all adjacent elements odd
function requiredOps( arr, N)
{
// Stores operations required for
// separating adjacent odd elements
let res1 = separate(arr, N, 0);
// Stores operations required for
// separating adjacent even elements
let res2 = separate(arr, N, 1);
// Maximum of two is the return
document.write(Math.max(res1, res2));
}
// Driver Code
// Given array arr[]
let arr = [ 13, 2, 6, 8, 3, 5,
7, 10, 14, 15 ];
// Size of array
let N = arr.length;
// Function Call
requiredOps(arr, N);
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por swatijha0908 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA