Dado un arreglo Arr[] de N enteros y un entero K , la tarea es encontrar si es posible igualar el conteo de elementos pares e impares realizando las siguientes operaciones como máximo K veces:
- Elija cualquier índice i tal que Arr[i] sea par y divídalo por 2.
- Elija cualquier índice i tal que Arr[i] sea impar y multiplíquelo por 2.
Ejemplos :
Entrada : Arr[] = {1, 4, 8, 12}, K = 2
Salida : Sí
Explicación : Recuento de impares = 1, Recuento de pares = 3.
Si hacemos la mitad de 4 dos veces, entonces 4 se convierte en 1 o si hacemos la mitad de 12 dos veces, luego se convierte en 3.
Es posible hacer que pares e impares cuenten igual realizando 2 operaciones.Entrada : Arr[] = {1, 2, 3, 4}, K = 0
Salida : Sí
Enfoque : La idea para resolver este problema es la siguiente:
Encuentre el conteo de elementos pares e impares (digamos expresados como CE y CO respectivamente).
El número de elementos necesarios para modificar = abs(CE – CO)/2 .
Un carácter par necesitaba dividirse a la mitad i veces si su bit más a la derecha está en (i+1) la ésima posición desde la derecha. Y un elemento impar puede hacerse par multiplicándolo por 2 en una sola operación.Use este criterio para encontrar el número de operaciones requeridas y si es como máximo K o no.
Siga los pasos a continuación para resolver el problema:
- Si N es impar, devuelve Falso.
- De lo contrario, inicialice un vector (digamos v ) de tamaño 32 con 0 para almacenar el recuento de bits más a la derecha en una posición, CE (Recuento de pares) = 0 y CO (Recuento de impares) = 0.
- Iterar a través de la array de 0 a N-1
- Encuentre CE y CO de Arr[]
- Encuentre el índice del bit establecido más a la derecha para cada elemento de array e incremente ese valor de índice del vector v .
- Si CE = CO, entonces no se requieren operaciones para igualar los recuentos.
- Si CO > CE, el resultado será (CO – CE)/2.
- De lo contrario, encuentre las operaciones requeridas iterando el vector.
- Devuelve verdadero si la operación requerida es menor que K. De lo contrario, devuelve falso .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to make even and odd element count same
// using at most K operations
bool findCount(int* arr, int N, int K)
{
// Edge Case
if (N & 1) {
return 0;
}
// Initialize the variables
int Res, CE = 0, CO = 0;
vector<int> v(32, 0);
// Find the index of rightmost set bit
// for every array element and increment
// that index of vector, also find even
// and odd count
for (int i = 0; i < N; i++) {
if (arr[i] & 1)
CO++;
else
CE++;
v[ffs(arr[i]) - 1]++;
}
// Condition is already true
if (CE == CO) {
Res = 0;
}
// Count of Even > Count of Odd
else if (CE > CO) {
int n = (CE - CO) / 2;
Res = 0;
// Find minimum operations to make the
// even and odd count equal
for (int i = 1; i < v.size(); i++) {
if (n >= v[i]) {
Res += v[i] * i;
n = n - v[i];
}
else {
Res += n * i;
break;
}
}
}
// Count of Odd > Count of Even
else {
Res = (CO - CE) / 2;
}
return Res <= K;
}
// Driver Code
int main()
{
int Arr[] = { 1, 4, 8, 12 };
int N = sizeof(Arr) / sizeof(Arr[0]);
int K = 2;
// Function Call
if (findCount(Arr, N, K))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
class GFG{
// Function to check if it is possible
// to make even and odd element count same
// using at most K operations
static boolean findCount(int []arr, int N, int K)
{
// Edge Case
if ((N & 1)>0) {
return false;
}
// Initialize the variables
int Res, CE = 0, CO = 0;
int []v = new int[32];
// Find the index of rightmost set bit
// for every array element and increment
// that index of vector, also find even
// and odd count
for (int i = 0; i < N; i++) {
if ((arr[i] & 1)>0)
CO++;
else
CE++;
v[arr[i] & (arr[i]-1) - 1]++;
}
// Condition is already true
if (CE == CO) {
Res = 0;
}
// Count of Even > Count of Odd
else if (CE > CO) {
int n = (CE - CO) / 2;
Res = 0;
// Find minimum operations to make the
// even and odd count equal
for (int i = 1; i < v.length; i++) {
if (n >= v[i]) {
Res += v[i] * i;
n = n - v[i];
}
else {
Res += n * i;
break;
}
}
}
// Count of Odd > Count of Even
else {
Res = (CO - CE) / 2;
}
return Res <= K;
}
// Driver Code
public static void main(String[] args)
{
int Arr[] = { 1, 4, 8, 12 };
int N = Arr.length;
int K = 2;
// Function Call
if (findCount(Arr, N, K))
System.out.print("Yes" +"\n");
else
System.out.print("No" +"\n");
}
}
// This code contributed by shikhasingrajput
Python3
# Python code to implement the above approach
# Function to check if it is possible
# to make even and odd element count same
# using at most K operations
def findCount(arr, N, K):
# Edge Case
if ((N & 1) != 0):
return 0
# Initialize the variables
Res = 0
CE = 0
CO = 0
v = [0]*32
# Find the index of rightmost set bit
# for every array element and increment
# that index of vector, also find even
# and odd count
for i in range(N):
if ((arr[i] & 1) != 0):
CO += 1
else:
CE += 1
v[arr[i] & (arr[i]-1) - 1] += 1
# Condition is already true
if (CE == CO):
Res = 0
# Count of Even > Count of Odd
elif (CE > CO):
n = (CE - CO) / 2
Res = 0
# Find minimum operations to make the
# even and odd count equal
for i in range(1, len(v)):
if (n >= v[i]):
Res += (v[i] * i)
n = n - v[i]
else:
Res += n * i
break
# Count of Odd > Count of Even
else:
Res = (CO - CE) / 2
return Res <= K
# Driver Code
if __name__ == "__main__":
Arr = [1, 4, 8, 12]
N = len(Arr)
K = 2
# Function Call
if findCount(Arr, N, K):
print("Yes")
else:
print("No")
# This code is contributed by Rohit Pradhan
Yes
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA