programa en C ++ para encontrar los números enteros que vienen número impar de veces en una matriz

En este programa C, vamos a aprender cómo averiguar números enteros que vienen número impar de veces en una matriz de enteros ?

Matriz de enteros es dada en la que un número (entero) debe repetir número impar de veces y tenemos que encontrar que un número entero.

Ejemplo:

    Input:
Array elements are: [1, 4, 6, 1, 9, 6, 4]
Output:
In this array output will be 9

Hay dos maneras de encontrar que:

1) Método de Naive

En este método vamos a tener que atravesar la matriz múltiple número de veces y considerar el suceso de cada número entero en ese array. Esta voluntad nos da O (n2) complejidad del tiempo como class cada número hay que recorrer todos los elementos n.

2) X-OR método

este método es la mejor ya que tiene O (n) la complejidad tiempo porque traverse la matriz sólo una vez para encontrar la solución. Este método utiliza la manipulación de bits.

    A    B    Y
0 0 0
0 1 1
1 0 1
1 1 0

ya que da cero como salida cuando dos mismos números se dan como entrada y cuando se les dará un número (por ejemplo x) y cero como entrada se le dará el mismo número (x) como salida.

Ahora vamos a tomar un ejemplo para que sea mucho más fácil de entender.

    [1, 4, 6, 1, 9, 6, 4]
At first result=0
Then,
0^1 = 1 result = 1
1^4 = 5 result = 5
5^6 = 3 result = 3
3^1 = 2 result = 2
2^9 = 11 result = 11
11^6 = 13 result = 13
13^4 = 9 result = 9

C ++ código:

#include <iostream>
#include <vector>
using namespace std;
//function to find odd integer
int oddInteger(vector <int> a)
{
int result=0;
for(unsigned int i=0;i<a.size();i++)
{
result=result^a[i];
}
return result;
}
//main function to test code
int main() {
int n;
//input total number of elements
cin >> n;
vector<int> a(n);
//read n numbers
for(int i=0;i<n;i++)
{
cin>>a[i];
}
//find and print result
int result = oddInteger(a);
cout << result << endl;
return 0;
}

salida

9


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *