Dada una array arr[] , la tarea es verificar si es posible reorganizar la array de tal manera que cada índice par ( indexación basada en 1 ) contenga un número par. Si tal reordenamiento no es posible, escriba “No”. De lo contrario, imprima «Sí» e imprima un arreglo posible
Ejemplos:
Entrada: arr[] = {2, 4, 8, 3, 1}
Salida:
Sí
3 4 8 2 1
Entrada: arr[] = {3, 3, 11, 8}
Salida: No
Explicación: Dado que la array contiene solo un elemento par, todos los índices pares no se pueden llenar con elementos pares.
Enfoque:
siga los pasos a continuación para resolver el problema:
- Cuente el número total de elementos pares presentes en la array dada. Si el conteo excede el número total de índices pares en la array dada, imprima «No».
- De lo contrario, escriba «Sí». Ahora, recorra la array usando dos punteros, i y j , apuntando a índices pares e impares respectivamente.
- Para cualquier i -ésimo índice que contenga un elemento impar, itere los índices impares utilizando j hasta que se encuentre un elemento par.
- Intercambiar a[i] y a[j]
- Repita los pasos anteriores hasta que todos los índices pares se llenen con un elemento par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it the
// array can be rearranged such
// such that every even indices
// contains an even element
void checkPossible(int a[], int n)
{
// Stores the count of even elements
int even_no_count = 0;
// Traverse array to count even numbers
for (int i = 0; i < n; i++)
{
if (a[i] % 2 == 0)
even_no_count++;
}
// If even_no_count exceeds
// count of even indices
if (n / 2 > even_no_count)
{
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
int j = 0;
for (int i = 1; i < n; i += 2)
{
if (a[i] % 2 == 0)
continue;
else
{
while (j < n && a[j] % 2 != 0)
j += 2;
a[i] += a[j];
a[j] = a[i] - a[j];
a[i] -= a[j];
}
}
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
checkPossible(arr, n);
return 0;
}
// This code is contributed by gauravrajput1
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if it the
// array can be rearranged such
// such that every even indices
// contains an even element
static void checkPossible(int a[])
{
// Stores the count of even elements
int even_no_count = 0;
// Traverse array to count even numbers
for (int i = 0; i < a.length; i++) {
if (a[i] % 2 == 0)
even_no_count++;
}
// If even_no_count exceeds
// count of even indices
if (a.length / 2 > even_no_count) {
System.out.println("No");
return;
}
System.out.println("Yes");
int j = 0;
for (int i = 1; i < a.length; i += 2) {
if (a[i] % 2 == 0)
continue;
else {
while (j < a.length && a[j] % 2 != 0)
j += 2;
a[i] += a[j];
a[j] = a[i] - a[j];
a[i] -= a[j];
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 5, 6, 7 };
checkPossible(arr);
}
}
Python3
# Python3 program to implement
# the above approach
# Function to check if it the
# array can be rearranged such
# such that every even indices
# contains an even element
def checkPossible(a, n):
# Stores the count of even elements
even_no_count = 0
# Traverse array to count even numbers
for i in range(n):
if (a[i] % 2 == 0):
even_no_count += 1
# If even_no_count exceeds
# count of even indices
if (n // 2 > even_no_count):
print("No")
return
print("Yes")
j = 0
for i in range(1, n, 2):
if (a[i] % 2 == 0):
continue
else:
while (j < n and a[j] % 2 != 0):
j += 2
a[i] += a[j]
a[j] = a[i] - a[j]
a[i] -= a[j]
for i in range(n):
print(a[i], end = " ")
# Driver Code
arr = [ 2, 3, 4, 5, 6, 7 ]
n = len(arr)
checkPossible(arr, n)
# This code is contributed by code_hunt
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to check if it the
// array can be rearranged such
// such that every even indices
// contains an even element
static void checkPossible(int []a)
{
// Stores the count of even elements
int even_no_count = 0;
// Traverse array to count even numbers
for (int i = 0; i < a.Length; i++)
{
if (a[i] % 2 == 0)
even_no_count++;
}
// If even_no_count exceeds
// count of even indices
if (a.Length / 2 > even_no_count)
{
Console.WriteLine("No");
return;
}
Console.WriteLine("Yes");
int j = 0;
for (int i = 1; i < a.Length; i += 2)
{
if (a[i] % 2 == 0)
continue;
else
{
while (j < a.Length && a[j] % 2 != 0)
j += 2;
a[i] += a[j];
a[j] = a[i] - a[j];
a[i] -= a[j];
}
}
for (int i = 0; i < a.Length; i++)
{
Console.Write(a[i] + " ");
}
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 2, 3, 4, 5, 6, 7 };
checkPossible(arr);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Java Script Program to implement
// the above approach
// Function to check if it the
// array can be rearranged such
// such that every even indices
// contains an even element
function checkPossible(a)
{
// Stores the count of even elements
let even_no_count = 0;
// Traverse array to count even numbers
for (let i = 0; i < a.length; i++) {
if (a[i] % 2 == 0)
even_no_count++;
}
// If even_no_count exceeds
// count of even indices
if (a.length / 2 > even_no_count) {
document.write("No<br>");
return;
}
document.write("Yes<br>");
let j = 0;
for (let i = 1; i < a.length; i += 2) {
if (a[i] % 2 == 0)
continue;
else {
while (j < a.length && a[j] % 2 != 0)
j += 2;
a[i] += a[j];
a[j] = a[i] - a[j];
a[i] -= a[j];
}
}
for (let i = 0; i < a.length; i++) {
document.write(a[i] + " ");
}
}
// Driver Code
let arr = [ 2, 3, 4, 5, 6, 7 ];
checkPossible(arr);
// This code is contributed by sravan kumar Gottumukkala
</script>
Producción:
Yes 3 2 5 4 7 6
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.