Competitive Programming

Q) Find a Element that is present once in an array and where every other element is present twice ?

INPUT : [1,3,5,5,6,1,6]

OUTPUT : 5

INPUT : [10,30,50,60,60,30,10]

OUTPUT : 50

FIRST APPROACH :

The very first approach is by using nested loop;

For Example say we have used for loop for expressing count of elements in an array;

NOTE : Considering the Time Complexity for the above example, in an array of n elements the loop is iterated n * n times. Hence, the time required to execute the solution is of a larger span.

Therefore, TIME COMPLEXITY : O ( n * n )

SECOND APPROACH :

The second approach you can consider is by using SORTING

We can sort the elements of an Array then compare it with next element;

NOTE : Considering the Time Complexity for the above example, in an array of n elements the loop is iterated n * log n times. Hence, the time required to execute the solution is of a smaller span compared to first approach.

Therefore, TIME COMPLEXITY : O( n * log n )

THIRD APPROACH:

The third approach goes with using HASHMAP algorithm;

The object map posses a pair showing count in value of the key

1. Map(4) {1 => 2, 2 => 2, 3 => 1, 6 => 2}
2. 0: {1 => 2}
3. 1: {2 => 2}
4. 2: {3 => 1}
5. 3: {6 => 2}

NOTE : Considering the Time Complexity for the above example, in an array of n elements the loop is iterated n times. Hence, the time required to execute the solution is much smaller compared to above approaches. Also to extract count from the object would require Space complexity of memory n.

Therefore, TIME COMPLEXITY : O( n ) SPACE COMPLEXITY : O( n )

Fourth Approach :

Making use of XOR for decreasing space complexity.

Now let’s understand how XOR works

For similar input BITS output is ZERO, and for dissimilar input BITS output is ONE.

Now relating with our example

So, 8 ^ 8 = 0 and 8 ^ 0 = 8

That is what we have used :

1 ^ 3 ^ 5 ^ 5 ^ 6 ^ 1 ^ 6 = 3

NOTE : Considering the Time Complexity for the above example, in an array of n elements the loop is iterated n times. Hence, the time required to execute the solution is much smaller compared to above approaches. Also to extract count from the object would require Space complexity of memory 1.

Therefore, TIME COMPLEXITY : O( n ) SPACE COMPLEXITY : O(1)