top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# Single Number II - InterviewBit Solution

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