**Single Number** is a problem statement that is based on **arrays** from **Data Structures and Algorithms**. In this problem, we can find the single number that occurs an **odd number of times** in the given array.

### The first approach to solve this problem is: Brute Force Algorithm

As you can see we have an array with size 5. To find the single number that occurring the odd number of times in this given array. So, we can **traverse from left to right side** of the array, one by one **select each element and compare** it with all the remaining elements of the array. If the selected element is equal to any **remaining elements** of the array, so for this we keep **one variable that is count variable** which is used to **increment it’s value by 1 each time** and If the count variable’s **value is odd**. It means, it is that single number which occurred the odd number of times in an array.

**So the output of this given array is 3.**

Let me explain it.

As you can see here, element 1 has **occurred 2 times**, not an odd number of times in this given array. So it is not a single number. Next, element 3 has **occurred 3 times/odd number of times** in this given array. That’s why the **output is 3** which means it is a **single number** that occurred the odd number of times in this given array.

By using a **brute force algorithm** the **time complexity is Big O (n2)**. Because we use **two loops**. The outer loop is used to **select each element one by one** from the given array. And the inner loop is used to compare that selected element of an array with all the remaining elements of the array. When the inner loop is completed we can check that the **count variable’s value is odd or not**.

So can we solve this problem less than **Big O(n****2****)**?

So the answer is yes. We can solve this problem using an **X-OR based solution**.

### The second approach to solve this problem is: X-OR Based Solution

So how X-OR works. Let me explain it to you.

X-OR is a very **powerful/magical bitwise operator**. It is part of **bit manipulation**. And by using X-OR, we can easily solve this problem in less than Big O(n2). X-OR means an Exclusive OR bitwise operator. **Bitwise** means it solves the problem **bit by bit**. The symbol of **X-OR is ^**. If both the inputs are the same then the output is 0 or exclude it. And if both inputs are different then the output is 1 or any nonzero value.

As you can see here, we have an array with size 5. Now we can apply **X-OR** to this given array and solve this problem **less than Big O(n****2****)**. Keep **one variable** that acts as an input and output that is **result variable** and **initialize** it with value 0.

Now, X-OR of 0 and 1 is 1. And the updated value of the result is 1. Next, X-OR of 1 and 3 is 2. And the updated value of the result is 2. Next, X-OR of 2 and 1 is 3. And the updated value of the result is 3. Next, X-OR of 3 and 3 is 0. And the updated value of the result is 0. And Next, X-OR of 0 and 3 is 3. And the updated value of the result is 3.

**So the output is 3. And that’s why we called X-OR as a Magical Bitwise Operator. **

By using an X-OR based solution, the **time complexity is Big O(n)**. Because we use only one loop. Loop is used to **traverse the whole array**. And by using this loop we can find the **X-OR** of the given array.

That means **X-OR based solution** is the **best solution or an optimized solution** of this given problem as it takes lesser time than the **brute force algorithm** to solve this problem.

### Now see the practical examples one by one for both the approaches.

#### Brute Force Algorithm Approach:

##### CODE:

##### OUTPUT:

Create one project and in main() function create one array and initialize it. And call the function from main(). Now provide the definition to the function that finds the single number. Provide **two parameters** to this function, one is an array and another is the size of the array. Now in this function create one **count variable and initialize it** with value 0.

Now create **two loops**. The **outer loop** is used to select each element one by one from the given array. In the **inner loop**, we create one if block that is used to compare each element with all the remaining elements of the array. If the **condition is true**, will increment the count value by 1. Now, we can check that the count variable’s value is odd or not. If the condition is true then return that single number to that function from where it is called. And then just print the output. Now **compile and run the program** and see the output.

**So the output is 3.**

#### X-OR Based Solution Approach:

##### CODE:

##### OUTPUT:

Create one project and in main() function create **one array and initialize** it. And call the function from main(). Now provide the definition to the function that finds the single number. Provide **two parameters** to this function, one is an array and another is the size of the array. Now in this function create one **result variable and initialize** it with value 0. Now create one loop. The loop is used to select each element one by one from the given array. Now perform **X-OR** with all the elements of the array. Once the loop is completed then just return the single number value to the function from where it is called. And then just print the output. Now **compile and run the program** and see the output.

**So the output is 3. **

So the **naive solution** of this problem is the **brute force algorithm** and the **best or an optimized** **solution** is **X-OR based solution**.

That’s all for now. Hope you have learned something through my Blog. I will see you in the next Data Structures and Algorithms blog. If you are interested in Data Structures and Algorithms, then you also opt for our exclusive **Brain Mentor’s Data Structures and Algorithms Online Course**.