Single Number II
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.
SIMILAR PROBLEMS
Pair Product Div by K
Posted: 15 May, 2022
Difficulty: Moderate
Left Rotate an Array by One
Posted: 17 May, 2022
Difficulty: Easy
Largest Element in the Array
Posted: 17 May, 2022
Difficulty: Easy
Check whether K-th bit is set or not
Posted: 20 May, 2022
Difficulty: Easy
Matrix Boundary Traversal
Posted: 20 May, 2022
Difficulty: Easy