Non-Repeating Element

Problem Statement: Non-Repeating Element

Given a sorted list of numbers in which all elements appear twice except one element that appears only once, find the number that appears only once.

Example:

arr[] = [1, 1, 2, 3, 3, 4, 4]

Output: 2

We have presented two approaches to solve the problem:

Approach 1: Brute Force

A Simple Solution is to use two loops. The outer loop picks elements one by one and inner loop checks if the element is present more than once or not. Time complexity will be O(n2) i.e. not the optimal one so we need to optimise it.

Approach 2: Efficient Using Xor trick

It requires some mathematical magic of bitwise operators. We would be using 2 properties of XOR operator ( ^ ) to solve this problem.

We know that A ^ A = 0 and A ^ 0 = A this implies that any integer when XOR'd with itself would give the result to be 0, and if any integer is XOR'd by 0 would give the result as the number itself. One must also know that XOR operator is commutative by nature.

Algorithm:

1. Initialize a variable result that would store the XOR'd result of all integers.

2. Iterate through the array from start to end.

3. XOR the new element with the previous result.

4. Once the loop completes, you would have the single non-repeating element. This approach would work because all the other elements in the array would have XOR'd to 0.

int singleNumber(int a[], int n) {
     //xor all numbers, the left over number would be the non repeated one
     // since the equl numbers cancel out each others bits
     int num = 0;
     for (int i = 0; i < n; ++i) {
         num ^= a[i];
     }
     return num;
    }

class Solution:
    def findelement(self, nums):
        xor = 0
        n = len(nums)
        for i in range(n):
            xor = xor ^ nums[i]
        return xor
ob1 = Solution()
print(ob1.findelement([1,1,2,3,3,4,4]))

Time Complexity: O(n)

Auxiliary Space: O(1)