Dada una array arr[] de tamaño N , la tarea es verificar si los elementos de la array se pueden reorganizar de tal manera que el XOR bit a bit del i-ésimo y (i+2)-ésimo elemento sea siempre 0 para cualquier valor de i ( 0 ≤ yo < N-2 )
Ejemplos:
Entrada: arr[] = {1, 1, 2, 2}, N = 4
Salida: SÍ
Explicación: Reorganice la array como {1, 2, 1, 2}.
Aquí XOR de [1, 1] y XOR de [2, 2] es 0.Entrada: arr[] = {1, 2, 3, 4}, N = 4
Salida: NO
Explicación: Aquí no es posible tal arreglo tal que arr[i] XOR arr[i+2] es 0.
Enfoque ingenuo: el enfoque ingenuo es reorganizar la array de todas las formas posibles y luego, para cada disposición, verificar si se cumple la condición dada.
Complejidad temporal: O(N *N!)
Espacio auxiliar: O(N)
Enfoque Eficiente: Este problema se puede resolver sobre la base de la siguiente idea:
Bitwise XOR de dos elementos es 0 solo cuando ambos elementos son iguales .
Con base en la observación anterior, se puede entender que todos los elementos en la posición impar deben ser iguales y todos los elementos en la posición par deben ser iguales.
Entonces, cuando solo hay un elemento único (porque todos los elementos serán iguales) o dos elementos únicos y sus frecuencias son las mismas que el número de posiciones pares e impares de la array, solo entonces es posible tal reordenamiento.
Siga los pasos que se mencionan a continuación para resolver el problema.
- Cree un mapa_desordenado para contar el número de elementos únicos.
- Atraviese la array y almacene los elementos de la array en el mapa.
- Cuente el número de diferentes tipos de elementos en el mapa.
- Si el recuento > 2 , entonces no es posible reorganizar la array por posición alternativa.
- Si cuenta = 1 , entonces el arreglo es posible.
- Si count = 2 , entonces hay ambas posibilidades:
- Si el tamaño de la array ( N ) es par, la frecuencia de ambos debería ser la misma.
- Si el tamaño de la array es impar, la frecuencia de un elemento debe ser N/2 y el otro debe ser N/2+1 .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check that rearrangement
// possible or not
bool find(int n, vector<int> arr)
{
// Declaring map
unordered_map<int, int> m;
int count = 0;
// Traversing array to check
// the number of unique element
for (int i = 0; i < n; i++) {
m[arr[i]]++;
if (m[arr[i]] == 1)
count++;
}
// Checking the number of different
// elements are greater than two or not
if (count > 2) {
return false;
}
else if (count == 0) {
return false;
}
else {
// If all the elements are same
if (count == 1) {
return true;
}
else {
// If size is odd
if (n % 2) {
if (m[arr[0]] == n / 2
|| m[arr[0]]
== (n / 2) + 1) {
return true;
}
else
return false;
}
// If size is even
else {
if (m[arr[0]] == n / 2)
return true;
else
return false;
}
}
}
return false;
}
// Driver code
int main()
{
// Size of Array
int N = 4;
vector<int> arr{ 1, 1, 2, 2 };
// Function call
bool flag = find(N, arr);
if (flag)
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG {
// Function to check that rearrangement
// possible or not
static boolean ans = false;
static void find(int n, int[] arr)
{
// Declaring map
HashMap<Integer, Integer> m = new HashMap<>();
int count = 0;
// Traversing array to check
// the number of unique element
for (int i = 0; i < n; i++) {
if(m.containsKey(arr[i]))
m.put(arr[i], m.get(arr[i]) + 1);
if (m.get(arr[i]) == null)count = count;
else count++;
}
// Checking the number of different
// elements are greater than two or not
if (count > 2) {
ans = false;
return;
}
else if (count == 0) {
ans = false;
return;
}
else {
// If all the elements are same
if (count == 1) {
ans = true;
return;
}
else {
// If size is odd
if (n % 2 == 1) {
if (m.get(arr[0]) == n / 2
|| m.get(arr[0])
== (n / 2) + 1) {
ans = true;
return;
}
else{
ans = false;
return;
}
}
// If size is even
else {
if (m.get(arr[0])== n / 2){
ans = true;
return;
}
else{
ans = false;
return;
}
}
}
}
}
// Driver code
public static void main (String[] args) {
int N = 4;
int arr[] = { 1, 1, 2, 2 };
// Function call
find(N, arr);
boolean flag = ans;
if (!flag)
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code to implement the approach
# Function to check that rearrangement
# possible or not
def find(n, arr):
# Declaring map
m = {}
count = 0
# Traversing array to check
# the number of unique element
for i in range(0, n):
if m.get(arr[i]) != None:
m[arr[i]] = m.get(arr[i])+1
else:
m[arr[i]] = 1
if m[arr[i]] == 1:
count += 1
# Checking the number of different
# elements are greater than two or not
if count > 2:
return False
elif count == 0:
return False
else:
# If all the elements are same
if count == 1:
return True
else:
# If size is odd
if n % 2 == 1:
if (m[arr[0]] == n / 2 or m[arr[0]] == (n / 2) + 1):
return True
else:
return False
# If size is even
else:
if m[arr[0]] == n / 2:
return True
else:
return False
return false
# Driver code
if __name__ == "__main__":
# Size of Array
N = 4
arr = [1, 1, 2, 2]
# Function call
flag = find(N, arr)
if flag == True:
print("YES")
else:
print("NO")
# This code is contributed by Rohit Pradhan
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check that rearrangement
// possible or not
static bool ans = false;
static void find(int n, int[] arr)
{
// Declaring map
Dictionary<int, int> m = new Dictionary<int, int>();
int count = 0;
// Traversing array to check
// the number of unique element
for (int i = 0; i < n; i++) {
if (m.ContainsKey(arr[i]))
m[arr[i]] += 1;
else
m[arr[i]] = 1;
count++;
}
// Checking the number of different
// elements are greater than two or not
if (count > 2) {
ans = false;
return;
}
else if (count == 0) {
ans = false;
return;
}
else {
// If all the elements are same
if (count == 1) {
ans = true;
return;
}
else {
// If size is odd
if (n % 2 == 1) {
if ((m[arr[0]] == (int)(n / 2))
|| (m[arr[0]]
== (int)(n / 2) + 1)) {
ans = true;
return;
}
else {
ans = false;
return;
}
}
// If size is even
else {
if (m[arr[0]] == (int)(n / 2)) {
ans = true;
return;
}
else {
ans = false;
return;
}
}
}
}
}
// Driver code
public static void Main(string[] args)
{
int N = 4;
int[] arr = { 1, 1, 2, 2 };
// Function call
find(N, arr);
bool flag = ans;
if (!flag)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript code for the above approach
// Function to check that rearrangement
// possible or not
function find(n, arr)
{
// Declaring map
let m = new Map();
let count = 0;
// Traversing array to check
// the number of unique element
for (let i = 0; i < n; i++) {
if (m.has(arr[i])) {
m.set(arr[i], m.get(arr[i]) + 1)
}
else {
m.set(arr[i], 1)
}
if (m.get(arr[i]) == 1)
count++;
}
// Checking the number of different
// elements are greater than two or not
if (count > 2) {
return false;
}
else if (count == 0) {
return false;
}
else {
// If all the elements are same
if (count == 1) {
return true;
}
else {
// If size is odd
if (n % 2) {
if (m.get(arr[0]) == Math.floor(n / 2)
|| m.get(arr[0])
== Math.floor(n / 2) + 1) {
return true;
}
else
return false;
}
// If size is even
else {
if (m.get(arr[0]) == Math.floor(n / 2))
return true;
else
return false;
}
}
}
return false;
}
// Driver code
// Size of Array
let N = 4;
let arr = [1, 1, 2, 2];
// Function call
let flag = find(N, arr);
if (flag)
document.write("YES");
else
document.write("NO");
// This code is contributed by Potta Lokesh
</script>
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shubhamrajput6156 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA