Dada una array ‘arr1’ de n enteros positivos. Los contenidos de arr1[] se copian a otra array ‘arr2’, pero los números se barajan y se elimina un elemento. Encuentre el elemento que falta (sin usar ningún espacio extra y en una complejidad de tiempo O(n)).
Ejemplos:
Input : arr1[] = {4, 8, 1, 3, 7}, arr2[] = {7, 4, 3, 1} Output : 8 Input : arr1[] = {12, 10, 15, 23, 11, 30}, arr2[] = {15, 12, 23, 11, 30} Output : 10
Una solución simple es considerar uno por uno cada elemento de la primera array y buscar en la segunda array. Tan pronto como encontramos un elemento faltante, regresamos. La complejidad temporal de esta solución es O(n 2 )
Una solución eficiente se basa en XOR. La ocurrencia combinada de cada elemento es dos veces, una en ‘arr1’ y otra en ‘arr2’, excepto un elemento que solo tiene una sola ocurrencia en ‘arr1’. Sabemos que (a Xor a) = 0. Entonces, simplemente haga XOR en los elementos de ambas arrays. El resultado será el número que falta.
Implementación:
C++
// C++ implementation to find the // missing number in shuffled array // C++ implementation to find the // missing number in shuffled array #include <bits/stdc++.h> using namespace std; // Returns the missing number // Size of arr2[] is n-1 int missingNumber(int arr1[], int arr2[], int n) { // Missing number 'mnum' int mnum = 0; // 1st array is of size 'n' for (int i = 0; i < n; i++) mnum = mnum ^ arr1[i]; // 2nd array is of size 'n - 1' for (int i = 0; i < n - 1; i++) mnum = mnum ^ arr2[i]; // Required missing number return mnum; } // Driver Code int main() { int arr1[] = {4, 8, 1, 3, 7}; int arr2[] = {7, 4, 3, 1}; int n = sizeof(arr1) / sizeof(arr1[0]); cout << "Missing number = " << missingNumber(arr1, arr2, n); return 0; }
Java
// Java implementation to find the // missing number in shuffled array class GFG { // Returns the missing number // Size of arr2[] is n-1 static int missingNumber(int arr1[], int arr2[], int n) { // Missing number 'mnum' int mnum = 0; // 1st array is of size 'n' for (int i = 0; i < n; i++) mnum = mnum ^ arr1[i]; // 2nd array is of size 'n - 1' for (int i = 0; i < n - 1; i++) mnum = mnum ^ arr2[i]; // Required missing number return mnum; } // Driver Code public static void main (String[] args) { int arr1[] = {4, 8, 1, 3, 7}; int arr2[] = {7, 4, 3, 1}; int n = arr1.length; System.out.println("Missing number = " + missingNumber(arr1, arr2, n)); } }
Python3
# Python3 implementation to find the # missing number in shuffled array # Returns the missing number # Size of arr2[] is n - 1 def missingNumber(arr1, arr2, n): # missing number 'mnum' mnum = 0 # 1st array is of size 'n' for i in range(n): mnum = mnum ^ arr1[i] # 2nd array is of size 'n - 1' for i in range(n - 1): mnum = mnum ^ arr2[i] # Required missing number return mnum # Driver Code arr1 = [4, 8, 1, 3, 7] arr2= [7, 4, 3, 1] n = len(arr1) print("Missing number = ", missingNumber(arr1, arr2, n)) # This code is contributed by Anant Agarwal.
C#
// C# implementation to find the // missing number in shuffled array using System; class GFG { // Returns the missing number // Size of arr2[] is n-1 static int missingNumber(int []arr1, int []arr2, int n) { // Missing number 'mnum' int mnum = 0; // 1st array is of size 'n' for (int i = 0; i < n; i++) mnum = mnum ^ arr1[i]; // 2nd array is of size 'n - 1' for (int i = 0; i < n - 1; i++) mnum = mnum ^ arr2[i]; // Required missing number return mnum; } // Driver Code public static void Main () { int []arr1 = {4, 8, 1, 3, 7}; int []arr2 = {7, 4, 3, 1}; int n = arr1.Length; Console.Write("Missing number = " + missingNumber(arr1, arr2, n)); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP implementation to find the // missing number in shuffled array // PHP implementation to find the // missing number in shuffled array // Returns the missing number // Size of arr2[] is n-1 function missingNumber($arr1, $arr2, $n) { // Missing number 'mnum' $mnum = 0; // 1st array is of size 'n' for ($i = 0; $i < $n; $i++) $mnum = $mnum ^ $arr1[$i]; // 2nd array is of size 'n - 1' for ($i = 0; $i < $n - 1; $i++) $mnum = $mnum ^ $arr2[$i]; // Required missing number return $mnum; } // Driver Code $arr1 = array(4, 8, 1, 3, 7); $arr2 = array(7, 4, 3, 1); $n = count($arr1); echo "Missing number = " , missingNumber($arr1, $arr2, $n); // This code is contributed by anuj_67. ?>
Javascript
<script> // Javascript implementation to find the // missing number in shuffled array // Javascript implementation to find the // missing number in shuffled array // Returns the missing number // Size of arr2[] is n-1 function missingNumber(arr1, arr2, n) { // Missing number 'mnum' let mnum = 0; // 1st array is of size 'n' for (let i = 0; i < n; i++) mnum = mnum ^ arr1[i]; // 2nd array is of size 'n - 1' for (let i = 0; i < n - 1; i++) mnum = mnum ^ arr2[i]; // Required missing number return mnum; } // Driver Code let arr1 = [4, 8, 1, 3, 7]; let arr2 = [7, 4, 3, 1]; let n = arr1.length; document.write("Missing number = " + missingNumber(arr1, arr2, n)); </script>
Missing number = 8
Complejidad temporal: O(n).
Complejidad espacial: O(1).
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA