Q:

C++ program to find the integers which come odd number of times in an array

belongs to collection: C++ programs on various topics

mahmoud2506
Save to bookmark
|
2022-05-05
|
  235 
0

Example:

    Input:
    Array elements are: [1, 4, 6, 1, 9, 6, 4]
    
    Output:
    In this array output will be 9
C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

There are two ways to find it:

1) Naive method

In this method we will have to traverse the array multiple number of times and count the occurrence of every integer in that array. This will gives us O(n2) time complexity as for every number we have to traverse all n elements.

2) X-OR method

This method is the best as it has O(n) time complexity because traverse the array only once to find the solution. This method uses bit manipulation.

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

As it gives zero as output when two same numbers are given as input and when a number (say x) and zero will be given as input it will give that same number (x) as output.

Now let’s take one example to make it much easier to understand.

    [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++ code:

#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;
}

Output

9

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C++ programs on various topics
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Vectors in C++ Standard Template Library (STL)... >>
<< Stack program using C++ Standard Template Library ...