Photo by Joshua Aragon on Unsplash

Bit By Bit: MISSING TWO

Contest Page | CodeChef

Problem Code: UNIBIT

Given an array of size 5X+3, where every element occurs 5 times, except one number, which occurs only 3 times. Find the element that occurs thrice.

Input:

The first line of input contains the T — number of test cases. Its followed by 2T lines, the first line contains N — the size of the array (of the form 5X + 3), and the second-line contains the elements of the array.

Output:

For each test case, print the number which occurs only once, separated by a new line.

Constraints

• 1≤T≤300
• 3≤N≤10⁴
• 1≤A[i]≤10⁹

Sample Input:

2
13
5 7 7 7 5 5 9 5 5 9 9 7 7
13
10 10 20 20 30 20 10 10 10 30 30 20 20

Sample Output:

9
30

EXPLANATION:

Bit manipulation technique:

Take the sum of each bit ( like 0,1,2,3,4,5…. 63 bits) of all elements of the array and divide the sum of each bit by 5.

If the sum is not divisible by five, then set the bit of the answer.

For example:

5 7 7 7 5 5 9 5 5 9 9 7 7

binary form:

0101 (5)
0111 (7)
0111 (7)
0111 (7)
0101 (5)
0101 (5)
1001 (9)
0101 (5)
0101 (5)
1001 (9)
1001 (9) 
0111 (7)
0111 (7)

sum of 0 bits -13

sum of 1st bits- 5

sum of 2nd bits-10

sum of 3rd bits-3

So, the sum of 0th bits & sum of 3rd bits are not divisible by 5 and set the 0th and 3rd bit

1001(bin) -> 9(dec)

answer: 9

Solution code (c++):

Time Complexity: O(n)

#include <bits/stdc++.h>
using namespace std;
typedef long long L;
L func(L arr[], int n)
{
L result = 0;
L x, sum;
for (L i = 0; i < 63; i++) {
  sum = 0;
  x = (1 << i);
  for (L j = 0; j < n; j++) 
  {
   if (arr[j] & x)
   sum++;
  }
  if ((sum % 5) != 0)
  result |= x;
 }
return result;
}
int main()
{
int t;
cin>>t;
while(t--){
 L n;
 cin>>n;
 L arr[n];
 for(L i=0;i<n;i++)
 {
   cin>>arr[i];
 }
 cout<<func(arr,n)<<endl;
 }
}