Dado un arreglo arr[] de tamaño N , la tarea es hacer que todos los elementos del arreglo sean impares eligiendo un subarreglo de longitud impar de arr[] e incrementar todos los elementos impares en 1 en este subarreglo. Imprime el conteo de tales operaciones requeridas.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 3, 5, 3, 2}
Salida: 2
Explicación:
En la primera operación, elija el subarreglo {2, 3, 4} e incremente todos sus elementos en posiciones impares, es decir , 1 y 3 de este subarreglo. La array actualizada es {3, 3, 5, 3, 5, 3, 2}.
En la segunda operación, elija el último índice que es un subarreglo de longitud 1 e incremente su valor. La array actualizada es {3, 3, 5, 3, 5, 3, 3}Entrada: arr[] = {1, 5, 7}
Salida: 0
Explicación: Dado que todos los elementos de la array son impares, no se requieren cambios.
Enfoque: La idea se basa en la observación de que cada vez que se elige un subarreglo, se cambian los valores de posición impar o los valores de posición par en el arreglo original. El problema se puede resolver eligiendo el subarreglo con avidez en cada operación. Primero, itere sobre todos los índices impares y marque el inicio del subarreglo tan pronto como se encuentre un valor par, y finalice el subarreglo cuando se encuentre un valor impar, actualizando simultáneamente el número de operaciones. Repita el mismo proceso para índices pares. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos flips , para almacenar la cantidad mínima de operaciones requeridas.
- Atraviese incluso los índices de la array arr[] realice los siguientes pasos:
- Si el elemento actual es impar , continúe iterando.
- De lo contrario, itere cada segundo elemento a partir de ese índice, hasta que se encuentre un elemento par. Después de completar el recorrido de la array o si se encuentra un elemento par, incremente los cambios en 1 .
- Repita el paso 2 para índices impares también.
- Después de completar los pasos anteriores, imprima el valor de flips como el número mínimo de operaciones según sea necesario.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum subarrays
// whose odd-indexed elements need to
// be incremented to make array odd
void minOperations(int arr[], int n)
{
// Stores the minimum number of
// operations required
int flips = 0;
// Iterate over even-indices
for (int i = 0; i < n; i += 2) {
// Check if the current
// element is odd
if (arr[i] % 2 == 1) {
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0) {
i += 2;
}
// Increment number of operations
flips++;
}
// Iterate over odd indexed
// positions of arr[]
for (int i = 1; i < n; i += 2) {
// Check if the current
// element is odd
if (arr[i] % 2 == 1) {
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0) {
i += 2;
}
// Increment the number
// of operations
flips++;
}
// Print the number of operations
cout << flips;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 3, 5, 3, 2 };
int N = sizeof(arr) / sizeof(int);
// Function Call
minOperations(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count minimum subarrays
// whose odd-indexed elements need to
// be incremented to make array odd
static void minOperations(int arr[], int n)
{
// Stores the minimum number of
// operations required
int flips = 0;
// Iterate over even-indices
for(int i = 0; i < n; i += 2)
{
// Check if the current
// element is odd
if (arr[i] % 2 == 1)
{
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0)
{
i += 2;
}
// Increment number of operations
flips++;
}
// Iterate over odd indexed
// positions of arr[]
for(int i = 1; i < n; i += 2)
{
// Check if the current
// element is odd
if (arr[i] % 2 == 1)
{
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0)
{
i += 2;
}
// Increment the number
// of operations
flips++;
}
// Print the number of operations
System.out.println(flips);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 3, 5, 3, 2 };
int N = arr.length;
// Function Call
minOperations(arr, N);
}
}
// This code is contributed by jana_sayantan
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count minimum subarrays
// whose odd-indexed elements need to
// be incremented to make array odd
static void minOperations(int []arr, int n)
{
// Stores the minimum number of
// operations required
int flips = 0;
// Iterate over even-indices
for(int i = 0; i < n; i += 2)
{
// Check if the current
// element is odd
if (arr[i] % 2 == 1)
{
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0)
{
i += 2;
}
// Increment number of operations
flips++;
}
// Iterate over odd indexed
// positions of []arr
for(int i = 1; i < n; i += 2)
{
// Check if the current
// element is odd
if (arr[i] % 2 == 1)
{
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0)
{
i += 2;
}
// Increment the number
// of operations
flips++;
}
// Print the number of operations
Console.WriteLine(flips);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 3, 4, 3, 5, 3, 2 };
int N = arr.Length;
// Function Call
minOperations(arr, N);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach # Function to count minimum subarrays # whose odd-indexed elements need to # be incremented to make array odd def minOperations(arr, n) : # Stores the minimum number of # operations required flips = 0; i = 0; # Iterate over even-indices while i < n : # Check if the current # element is odd if (arr[i] % 2 == 1) : i += 2; # If true, continue continue; # Otherwise, mark the starting # of the subarray and iterate # until i < n and arr[i] is even while (i < n and arr[i] % 2 == 0) : i += 2; # Increment number of operations flips += 1; i += 2; # Iterate over odd indexed # positions of arr[] i = 1 while i < n : # Check if the current # element is odd if (arr[i] % 2 == 1) : i += 2; # If true, continue continue; # Otherwise, mark the starting # of the subarray and iterate # until i < n and arr[i] is even while (i < n and arr[i] % 2 == 0) : i += 2; # Increment the number # of operations flips += 1; i += 2; # Print the number of operations print(flips); # Driver Code if __name__ == "__main__" : arr = [ 2, 3, 4, 3, 5, 3, 2 ]; N = len(arr); # Function Call minOperations(arr, N); # This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to count minimum subarrays
// whose odd-indexed elements need to
// be incremented to make array odd
function minOperations(arr, n)
{
// Stores the minimum number of
// operations required
let flips = 0;
// Iterate over even-indices
for(let i = 0; i < n; i += 2)
{
// Check if the current
// element is odd
if (arr[i] % 2 == 1)
{
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0)
{
i += 2;
}
// Increment number of operations
flips++;
}
// Iterate over odd indexed
// positions of arr[]
for(let i = 1; i < n; i += 2)
{
// Check if the current
// element is odd
if (arr[i] % 2 == 1)
{
// If true, continue
continue;
}
// Otherwise, mark the starting
// of the subarray and iterate
// until i < n and arr[i] is even
while (i < n && arr[i] % 2 == 0)
{
i += 2;
}
// Increment the number
// of operations
flips++;
}
// Print the number of operations
document.write(flips);
}
// Driver Code
let arr = [ 2, 3, 4, 3, 5, 3, 2 ];
let N = arr.length;
// Function Call
minOperations(arr, N);
// This code is contributed by souravghosh0416.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ankushingle8523 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA