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(n2)?
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.
Read Full Article – https://brain-mentors.com/single-number-arrays-data-structures-and-algorithms/