Last Updated: 14 Jan, 2021
Single Number II
Easy
Asked in companies
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.
Approaches
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.
- 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.
- 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.
Similar problems