Programa C/C++ para encontrar el número que ocurre un número impar de veces

Dada una array arr[] que consiste en números enteros positivos que ocurren un número par de veces, excepto un número, que ocurre un número impar de veces. La tarea es encontrar este número impar de veces que ocurre el número.

Ejemplos:  

Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3

Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5

Enfoque ingenuo: una solución simple es ejecutar dos bucles anidados. El ciclo externo selecciona todos los elementos uno por uno y el ciclo interno cuenta el número de ocurrencias del elemento seleccionado por el ciclo externo. 

Implementación:

// C++ program to find the element
// occurring odd number of times
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the element
// occurring odd number of times
int getOddOccurrence(int arr[], int arr_size)
{
    for (int i = 0; i < arr_size; i++) {
 
        int count = 0;
 
        for (int j = 0; j < arr_size; j++) {
            if (arr[i] == arr[j])
                count++;
        }
        if (count % 2 != 0)
            return arr[i];
    }
    return -1;
}
 
// driver code
int main()
{
    int arr[] = { 2, 3, 5, 4, 5, 2,
                  4, 3, 5, 2, 4, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function calling
    cout << getOddOccurrence(arr, n);
 
    return 0;
}

// C program to find the element
// occurring odd number of times
#include <stdio.h>
 
// Function to find the element
// occurring odd number of times
int getOddOccurrence(int arr[], int arr_size)
{
    for(int i = 0; i < arr_size; i++)
    {
        int count = 0;
 
        for(int j = 0; j < arr_size; j++)
        {
            if (arr[i] == arr[j])
                count++;
        }
        if (count % 2 != 0)
            return arr[i];
    }
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, 5, 4, 5, 2,
                  4, 3, 5, 2, 4, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function calling
    printf("%d",getOddOccurrence(arr, n));
     
    return 0;
}
 
// This code is contributed by rbbansal

5

Complejidad temporal: O(N ² )  
Espacio auxiliar: O(1)

Mejor enfoque: una mejor solución es usar Hashing . Utilice elementos de array como clave y sus recuentos como valor. Cree una tabla hash vacía. Uno por uno, recorra los elementos de array dados y almacene los recuentos. La complejidad temporal de esta solución es O(n). Pero requiere espacio adicional para el hashing.
Complejidad temporal: O(N)  
Espacio auxiliar: O(N)

Enfoque eficiente: la mejor solución es hacer XOR bit a bit de todos los elementos. XOR de todos los elementos nos da un elemento extraño. Tenga en cuenta que XOR de dos elementos es 0 si ambos elementos son iguales y XOR de un número x con 0 es x.

A continuación se muestra la implementación del enfoque anterior.  

// C++ program to find the element
// occurring odd number of times
#include <bits/stdc++.h>
using namespace std;
 
// Function to find element occurring
// odd number of times
int getOddOccurrence(int ar[], int ar_size)
{
    int res = 0;
    for (int i = 0; i < ar_size; i++)
        res = res ^ ar[i];
 
    return res;
}
 
/* Driver function to test above function */
int main()
{
    int ar[] = { 2, 3, 5, 4, 5,
                 2, 4, 3, 5, 2,
                 4, 4, 2 };
    int n = sizeof(ar) / sizeof(ar[0]);
 
    // Function calling
    cout << getOddOccurrence(ar, n);
 
    return 0;
}

// C program to find the element
// occurring odd number of times
#include <stdio.h>
 
// Function to find element occurring
// odd number of times
int getOddOccurrence(int ar[], int ar_size)
{
    int res = 0;
    for (int i = 0; i < ar_size; i++)
        res = res ^ ar[i];
 
    return res;
}
 
/* Driver function to test above function */
int main()
{
    int ar[] = { 2, 3, 5, 4, 5,
                 2, 4, 3, 5, 2,
                 4, 4, 2 };
    int n = sizeof(ar) / sizeof(ar[0]);
 
    // Function calling
    printf("%d", getOddOccurrence(ar, n));
    return 0;
}

5

Complejidad de tiempo: O(N)  
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Encontrar el número que ocurre un número impar de veces para obtener más detalles.