Find the Number that Appears Once

Imagine an array with all elements appearing three times, with the exception of one, which appears just once. Find the item that only appears once. We should solve this problem in O(n) time complexity and O(1) additional space.

Examples

Input: arr[] = {2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5}

Output: 2

Except for 2, which only occurs once, every element in the input array appears three times.

Input: arr[] = {10, 19, 21, 20, 21, 10, 19, 19, 10}

Output: 20

Except for 20, which only occurs once, every element in the input array appears multiple times.

Sorting allows us to complete the task in O(n Logn) time. We may alternatively employ hashing, which uses more space but has a worst-case time complexity of O(n).

Approach - 1

The goal is to employ bitwise operators to provide an O(n)-time and O(1)-extra-space solution. Due to the odd number of appearances of all the components, the solution is not as straightforward as previous XOR-based methods.

For each element in the array, execute a loop. Keep the following two values constant at the conclusion of each iteration.

1. One: The parts that have appeared for the first, fourth, seventh, etc., times.
2. Two: The passages that have been read a second, fifth, eighth, etc., time.

We then provide the value of "one" back.

How to maintain the values of 'one' and 'two'?

We will initialize two variables 'one' and 'two' as 0. At each iteration, we will find the common bits between the current element and the previous value of 'one.' We will add these common bits to the variable 'two.' For this operation, we will use XOR. There would be some extra bits in two which we will remove later.

Update 'one' by doing XOR of the current element with the previous value of 'one.' Some bits may appear three times. We will remove these extra bits later.

Code

Output:

The element that occurs only once is 2

Time Complexity: The time complexity of this approach is O(n), where n is the number of elements in the array

Auxiliary Space: Since we have only created constants, this approach uses O(1) extra memory space.

Approach - 2

Here is another approach that has an O(n) time complexity and takes O(1) more space. For all the integers, we can add the bits present in the same position, and we can take the modulo of that sum with 3. The bits of the number that occur only once are those whose total is not a multiple of three.

For example, we will consider [6, 6, 6, 8] as an array. The 110, 110, 110, 1000

(Sum of the first bits) % 3 = (0 + 0 + 0 + 0) % 3 = 0;

(Sum of the second bits) % 3 = (1 + 1 + 1 + 0) % 3 = 0;

(Sum of the third bits) % 3 = (1 + 1 + 1 + 0) % 3 = 0;

(Sum of the fourth bits) % 3 = (1) % 3 = 1;

Hence the number which occurs only once in 1000 bits

Note: This algorithm will not work for negative numbers

Here is the implementation of this algorithm:

Code

Output:

The element that occurs only once is 2

Time Complexity: The time complexity of this approach is O(n), where n is the number of elements in the array

Auxiliary Space: Since we have only created constants, this approach uses O(1) extra memory space.

Approach - 3

In the third approach, we will use the following formula

( 3 * (sum_of_distinct_array_elements) - (sum_of_all_array_elements) ) / 2

Let the array[] = [2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5, 3, 1]

summ = (3 * (sum_of_distinct_array_elements) - (sum_of_all_array_elements)) / 2

= (3 * (2 + 5 + 6 + 1 + 3) - (2 + 5 + 6 + 6 + 5 + 1 + 3 + 3 + 5 + 1 + 1 + 5 + 3 + 1)) / 2

= (3 * 17 - 47) / 2

= (51 - 47) / 2

= 2 (this is the required answer)

We know that the set data structure does not contain duplicate elements. We will use this data structure to find the sum of distinct elements of the array. However, the insertion process on this data structure has the worst-case cost of O(log(n)). Here, we'll be utilizing Python sets.

Here is the implementation of this algorithm:

Code

Output:

The element that occurs only once is 2

Time Complexity: O(N log(N))

Auxiliary Space: O(N)

Approach - 4

The last approach is using the Counter function

Using a Counter is the most straightforward approach. Below is the algorithm of this approach.

We will find the frequency of each element of the array using the Counter function

We will traverse through the Counter dictionary, and using the if condition, we will check if the current key has its value = 1

If the key has value 1 then we will return that key

Here is the implementation of this approach

Code

Output:

The element that occurs only once is 2

Time Complexity: O(N)

Auxiliary Space: O(1)

Method #5 : Using count() method.

We can find the occurrence of elements using count() method. If count() method returns 1 then the element has a single occurrence.

• C++
• Java
• Python3
• C#
• Javascript

Output:

The element with single occurrence is  2

Time Complexity: O(n^2)

Auxiliary Space: O(1)