Dada una array arr[] de tamaño N , la tarea es igualar todos los elementos de la array reemplazando un par de elementos adyacentes con su suma.
Ejemplos:
Entrada: arr[] = { 2, 4, 5, 11, 6 }
Salida: 1
Explicación:
Reemplazar un par (arr[2], arr[3]) con su suma ( = 5 + 11 = 16) modifica arr[ ] a { 2, 4, 16, 16, 6 }
Dado que todos los elementos del arreglo son pares, la salida requerida es 1.Entrada: arr[] = { 1, 2, 4, 3, 11 }
Salida: 3
Explicación:
Reemplazar el par (arr[3], arr[4]) y reemplazarlos con su suma ( = 3 + 11 = 14) modifica arr[] a { 1, 2, 4, 14, 14 }
Reemplazando el par (arr[0], arr[1]) y reemplazándolos con su suma ( = 1 + 2 = 3) modifica arr[] a { 3, 3, 4, 14, 14 }
Reemplazar el par (arr[0], arr[1]) con su suma ( = 3 + 3 = 6) modifica arr[] a { 6, 6, 4, 14, 14 }.
Por lo tanto, la salida requerida es 3.
Enfoque: La idea es utilizar el hecho de que la suma de dos números impares genera un número par . Siga los pasos a continuación para resolver el problema:
- Inicialice dos enteros, digamos res , para contar el número de reemplazos y odd_continuous_segment , para contar el número de números impares continuos
- Recorra la array y verifique las siguientes condiciones para cada elemento de la array:
- Si arr[i] es impar , entonces incremente la cuenta de segmento_continuo_impar en 1
- De lo contrario, si odd_continuous_segment es impar, entonces incremente res por odd_continuous_segment/2 . De lo contrario, incremente res por odd_continuous_segment / 2 + 2 y asigne odd_continuous_segment a 0 .
- Compruebe si odd_continuous_segment es impar . Si se encuentra que es cierto, entonces incremente res por odd_continuous_segment / 2 . De lo contrario, incremente la resolución en (odd_continuous_segment / 2 + 2)
- Finalmente, imprima el valor obtenido de res
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
// Function to find minimum count of operations
// required to make all array elements even
int make_array_element_even(int arr[], int N)
{
// Stores minimum count of replacements
// to make all array elements even
int res = 0;
// Stores the count of odd
// continuous numbers
int odd_cont_seg = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If arr[i] is an odd number
if (arr[i] % 2 == 1) {
// Update odd_cont_seg
odd_cont_seg++;
}
else {
if (odd_cont_seg > 0) {
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0) {
// Update res
res += odd_cont_seg / 2;
}
else {
// Update res
res += (odd_cont_seg / 2) + 2;
}
// Reset odd_cont_seg = 0
odd_cont_seg = 0;
}
}
}
// If odd_cont_seg exceeds 0
if (odd_cont_seg > 0) {
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0) {
// Update res
res += odd_cont_seg / 2;
}
else {
// Update res
res += odd_cont_seg / 2 + 2;
}
}
// Print the result
return res;
}
// Drivers Code
int main()
{
int arr[] = { 2, 4, 5, 11, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << make_array_element_even(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find minimum count of operations
// required to make all array elements even
static int make_array_element_even(int arr[], int N)
{
// Stores minimum count of replacements
// to make all array elements even
int res = 0;
// Stores the count of odd
// continuous numbers
int odd_cont_seg = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// If arr[i] is an odd number
if (arr[i] % 2 == 1)
{
// Update odd_cont_seg
odd_cont_seg++;
}
else
{
if (odd_cont_seg > 0)
{
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0)
{
// Update res
res += odd_cont_seg / 2;
}
else
{
// Update res
res += (odd_cont_seg / 2) + 2;
}
// Reset odd_cont_seg = 0
odd_cont_seg = 0;
}
}
}
// If odd_cont_seg exceeds 0
if (odd_cont_seg > 0)
{
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0)
{
// Update res
res += odd_cont_seg / 2;
}
else
{
// Update res
res += odd_cont_seg / 2 + 2;
}
}
// Print the result
return res;
}
// Drivers Code
public static void main(String[] args)
{
int arr[] = { 2, 4, 5, 11, 6 };
int N = arr.length;
System.out.print(make_array_element_even(arr, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to implement # the above approach # Function to find minimum count of operations # required to make all array elements even def make_array_element_even(arr, N): # Stores minimum count of replacements # to make all array elements even res = 0 # Stores the count of odd # continuous numbers odd_cont_seg = 0 # Traverse the array for i in range(0, N): # If arr[i] is an odd number if (arr[i] % 2 == 1): # Update odd_cont_seg odd_cont_seg+=1 else: if (odd_cont_seg > 0): # If odd_cont_seg is even if (odd_cont_seg % 2 == 0): # Update res res += odd_cont_seg // 2 else: # Update res res += (odd_cont_seg // 2) + 2 # Reset odd_cont_seg = 0 odd_cont_seg = 0 # If odd_cont_seg exceeds 0 if (odd_cont_seg > 0): # If odd_cont_seg is even if (odd_cont_seg % 2 == 0): # Update res res += odd_cont_seg // 2 else: # Update res res += odd_cont_seg // 2 + 2 # Print the result return res # Drivers Code arr = [2, 4, 5, 11, 6] N = len(arr) print(make_array_element_even(arr, N)) # This code is contributed by shubhamsingh10
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Function to find minimum count of operations
// required to make all array elements even
static int make_array_element_even(int []arr, int N)
{
// Stores minimum count of replacements
// to make all array elements even
int res = 0;
// Stores the count of odd
// continuous numbers
int odd_cont_seg = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// If arr[i] is an odd number
if (arr[i] % 2 == 1)
{
// Update odd_cont_seg
odd_cont_seg++;
}
else
{
if (odd_cont_seg > 0)
{
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0)
{
// Update res
res += odd_cont_seg / 2;
}
else
{
// Update res
res += (odd_cont_seg / 2) + 2;
}
// Reset odd_cont_seg = 0
odd_cont_seg = 0;
}
}
}
// If odd_cont_seg exceeds 0
if (odd_cont_seg > 0)
{
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0)
{
// Update res
res += odd_cont_seg / 2;
}
else
{
// Update res
res += odd_cont_seg / 2 + 2;
}
}
// Print the result
return res;
}
// Drivers Code
public static void Main(String[] args)
{
int []arr = { 2, 4, 5, 11, 6 };
int N = arr.Length;
Console.Write(make_array_element_even(arr, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find minimum count of operations
// required to make all array elements even
function make_array_element_even(arr, N)
{
// Stores minimum count of replacements
// to make all array elements even
let res = 0;
// Stores the count of odd
// continuous numbers
let odd_cont_seg = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
// If arr[i] is an odd number
if (arr[i] % 2 == 1)
{
// Update odd_cont_seg
odd_cont_seg++;
}
else
{
if (odd_cont_seg > 0)
{
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0)
{
// Update res
res += odd_cont_seg / 2;
}
else
{
// Update res
res += (odd_cont_seg / 2) + 2;
}
// Reset odd_cont_seg = 0
odd_cont_seg = 0;
}
}
}
// If odd_cont_seg exceeds 0
if (odd_cont_seg > 0)
{
// If odd_cont_seg is even
if (odd_cont_seg % 2 == 0)
{
// Update res
res += odd_cont_seg / 2;
}
else
{
// Update res
res += odd_cont_seg / 2 + 2;
}
}
// Print the result
return res;
}
// Driver Code
// Given array arr[]
let arr = [ 2, 4, 5, 11, 6 ];
let N = arr.length;
document.write(make_array_element_even(arr, N));
// This code is contributed by splevel62
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)