# Element that appears once

Posted: 14 Jan, 2021

Difficulty: Easy

#### You are given an arbitrary array ‘arr’ consisting of N non-negative integers, where every element appears thrice except one. You need to find the element that appears only once.

##### Input Format:

```
The first line of the input contains a single integer T, representing the number of test cases.
The first line of each test case consists of a single integer N, representing the number of elements in the given array.
The second line of each test case contains N space-separated integers, denoting the elements of the array.
```

##### Output Format:

```
For each test case, print a single integer representing the element that appears only once in the array.
```

##### Note:

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 100
4 <= N <= 10^4
0 <= arr[i] < 10^9
Time Limit: 1sec
```

##### Follow Up:

```
Try to solve this problem in O(N) time and O(1) space complexity.
```

Approach 1

Approach 2

- We can also solve this problem by formulating a mathematical equation between the actual sum of elements in the array, and the sum of elements if each element was counted only once.
- For example, let the elements of the array be [a, a, a, b, b, b, c, c, c, d]. Here, all elements except d is appearing thrice.
- FIrst we find out the sum of actual elements of the array, arrSum = (a + a + a + b + b + b + c + c + c + d).
- Then, find the sum of elements, with each element considered only once, setSum = (a + b + c + d), by creating a set from the input array.
- By looking carefully and solving for d, we get the following relation:-

d = ((3 * setSum) - arrSum) / 2. - We can extend the same logic for any arbitrary array with any number of elements.

Approach 3

- We can utilize bit manipulation to solve this problem.
- For each bit position i, we count the number of elements whose ith bit is set. Let this be ‘count’.
- For bit positions where (count % 3) is equal to 0, it means that the current bit is set in 3 * x elements of the array, where x is an arbitrary number.
- Hence, if (count % 3) = 0, then the current bit cannot be set in the required number(because it appears only once, hence the remainder should be 1).
- For bit positions where (count % 3) is 1, the current bit will be set in the answer.
- Using the above logic, we can loop over all the bit positions (0 to 31) and find out the set bits in the final result.
- Once we know the set bits, we can easily form the answer from them.