Single Number | Arrays | Data Structures and Algorithms

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.

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(n2). 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.

Read Full Article – Single Number | Arrays | Data Structures and Algorithms

Brain Mentors Pvt. Ltd. started with a mission to link the IT industry and educational institutions. We aim to transform our every student into an IT professional who is ready to be employed in the industry.