Unique Number-III Problem asked in interviews based on Bitmasking Concepts.

Read and Try Unique Number-III first yourself. Try now at HackerBlocks

Video Solution by Prateek Narang

Difficulty:

Medium

Concepts Used:

Bitmasking

Statement:

Given a list of numbers where every number is occuring thrice except one number we have to find out the unique number which is occuring just one time.

Explanation

Since all other numbers are occuring thrice, we need to cancel all the bits occuring thrice(contriubted by repeating numbers) - so we take sum of bits at every positions(in all numbers) and take mod by 3 for every position. We maintain a array of size 64 to handle 64 bit integers. Watch the video to learn more.

Solution

#include<iostream>
using namespace std;

int findUniqueNo(int *a,int n){
     int cnt[64] = {0};

     for(int j=0;j<n;j++){
        ///Extract Bits of Every Number and update the count array

        int i=0;
        int no = a[j];
        while(no>0){
            cnt[i] += (no&1);
            i++;
            no = no>>1;
        }

     }
     /// Take mod of cnt array with 3
     int p = 1;
     int ans = 0;
     for(int i=0;i<64;i++){
        cnt[i] %= 3;

        ans += cnt[i]*p;
        p = p<<1;
     }
    return ans;



}

int main(){
    int a[] = {7,7,3,4,12,6,6,6,3,3,4,4,7};
    int n = sizeof(a)/sizeof(int);

    cout<< findUniqueNo(a,n);


return 0;
}