All Repeating Three Times Except One
1. You are given an array of numbers.Input Format
2. All numbers occur thrice in the array except one.
3. You have to find the element that occurs once.
A number nOutput Format
a1
a2..
n numbers
A numberQuestion Video
1 <= n <= 10^9Sample Input
1 <= a1,a2.. <= 10^9
4Sample Output
1 1 1 2
2

Editorial
In this problem, we are provided with an array of numbers where all elements except one repeat thrice, so we need to find the unique element using bit manipulation.
Insight: Suppose we remove the unique number from our array. Then we have a set of elements that repeats thrice with no exception. Now we wish to calculate the number of set bits at every position for this array. Now the point here is to observe that if an element has a set bit at index i then it means that its frequency will be 3 for that particular element, this ensures that if we take the sum of all the numbers in this array for every index then the result will be having bits frequencies in multiples of three.
Now a bit manipulation approach surrounding the above insight is to use the count of the set bit at every index if the number of set bits at a particular index is of type 3x + 1 then we have a set bit at that position for our unique element, else we have an unset bit.
So we iterate from 0 to 31 and for every index, we iterate over the entire array to check for the number of set bits, hence our total time complexity becomes O(32*n).
For example:
N = 10
51 > 1 1 0 0 1 1
57 > 1 1 1 0 0 1
51 > 1 1 0 0 1 1
63 > 1 1 1 1 1 1
57 > 1 1 1 0 0 1
57 > 1 1 1 0 0 1
51 > 1 1 0 0 1 1
63 > 1 1 1 1 1 1
38 > 1 0 0 1 1 0
63 > 1 1 1 1 1 1
Sum 1096479
Res >100110 => 38
We can optimize this code even further and can attain a time complexity of O(n).
To achieve this in O(n) time complexity we will be maintaining three integers say ones, twos, and threes which will be representing the bits frequencies of type 3x + 1, 3x + 2, and 3x respectively. Now we will start considering every element of the array one by one and update the counts of bits in these arrays. Say at some point we have the count of bits as 4 3 1 0 5 5 then we would have values of ones, twos, and threes as:
ones = 1 0 1 0 0 0
twos = 0 0 0 0 1 1
threes = 0 1 0 1 0 0
This represents that we have bits count of type 3x + 1 at indexes 0 and 2. Similarly, we have the bit count of type 3x + 2 at indexes 4 and 5 and the bit count of type 3x at indexes 1 and 3.
Now while traversing the array we will be updating these count bits and when we reach the end of the array we will be returning ones as our result, as ones are of the type 3x + 1 so this will be storing our unique number.
Time Complexity: O(n)
The time complexity for the function is linear as we are traversing on every element only once.
Space Complexity: O(1)
The space complexity for the function is constant.

Asked in Companies

Related Topics