Element that appears once
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

Question

Element that appears once

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.

Accepted Answer

Store the count of all the elements

An easy way to solve this problem is to first store the count of all the elements in a map with keys as elements of the array and value as their frequencies. Then iterate through the map to find out the element whose frequency is 1.

Space Complexity: O(n)Explanation:

O(N),

Since we are using extra space for storing the count of elements in a separate data structure.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where N is the number of elements in the array.

Accepted Answer

Try to form a mathematical relation to solve this problem

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.

Space Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

Since we are creating a set from the array elements.

Time Complexity: O(nlogn)Explanation:

O(N * logN), where N is the number of elements in the array.

Accepted Answer

Use bit manipulation.

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.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant extra space.

Time Complexity: O(n)Explanation:

O(32 * N), where N is the number of elements in the array.

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:

Output Format:

Note:

Constraints:

Follow Up:

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer