Single Number II - InterviewBit Solution

Problem: Single Number II

Problem Description:

Given an array of integers, every element appears thrice except for one which occurs once.

Find that element that does not appear thrice.

Note: Your algorithm should have a linear runtime complexity.

Could you implement it without using extra memory?

Input Format:

First and only argument of input contains an integer array A 

Output Format:

    return a single integer. 

Constraints:

2 <= N <= 5 000 000   
0 <= A[i] <= INT_MAX

For Examples :

Example Input 1:
    A = [1, 2, 4, 3, 3, 2, 2, 3, 1, 1]
Example Output 1:
    4
Explanation:
    4 occur exactly once
Example Input 2:
    A = [0, 0, 0, 1]
Example Output 2:
    1

Solution Approach:

If every number appears thrice then if count the set bits at every position then at every position the count will be divisible by 3. But if we add another number that doesn't appear 3 times or the multiple of three times then the count of set bits at some positions will not be divisible by 3. We can get our result by storing those set bits.

Time & Space Complexity:

Time Complexity: O(32*N) -> O(N)
Space Compleixty: O(32) -> O(1)

Solution:

Code in C++

If you have any questions or queries, feel free to drop a comment in the comments section below.

Note: Help us improve this blog

If you have a better solution, and you think you can help your peers to understand this problem better, then please drop your solution and approach in the comments section below.

We will upload your approach and solution here by giving you the proper credit so that you can showcase it among your peers.