C++ O(n) - time O(1) - Space Easy to understand


#1

int Solution::singleNumber(const vector &A) {

// considering a 32 bit integer as answer 
int dp[33] = {0};

// pre- calculating powers of 2
int two_powers[33]={0};
int m = 1;

for(int i = 0; i <= 32 ; i++)
{
    
    two_powers[i] = m;
    m *=2;
    
    
}
// store the frequency of set bits at all positions 
for(int i =0 ; i < A.size() ; i++)
{
    int temp = A[i];
    int j = 0;
    
    while(temp)
    {
        
        if(temp&1)
        dp[j]++;
        
        
        temp = temp>>1;
        j++;
        
         
    }
    
}

int ans = 0;


for(int i = 0; i <= 32; i++)
{
    // if the frequency at this bit position is not divisible by 3 , it mean this bit position was 1 for the number we are trying to find
    if(dp[i]%3!=0)
    {
        ans += two_powers[i];
        
    }
    
    
}
return ans;

}