top of page
Search

# 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.