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