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

In this C program, we are going to learn **how to find out integers which come odd number of times in an integer array**?

Submitted by Shubham Singh Rajawat, on January 21, 2018

An array of integers is given in which one number (integer) must repeat odd number of times and we have to find that one integer.

**Example:**

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

**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(n^{2}) 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 Y0 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL