[Leetcode problems]137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2] Output: 3

Compared to [Leetcode problems]136. Single Number, this problem sets all other number to appear 3 times. To achieve O(n) time complexity and O(1) space complexity, we again need bitwise operators.

Logic

Let’s consider these numbers expressed in binary format. For each bit digit, we would count how many numbers have 1 there, and mod it against 3. Since only 1 item appears once, and all others appear three times, then:

  • if the single number has 1 on that position, then there should be 3*x+1 1s. After taking mod against 3, the result is 1.
  • if the single number has 0 on that position, then there should be 3*x 1s. After taking mod against 3, the result is 0.

Implementation

We can definitely maintain an array arr with the size of 32 where arr[i] corresponding to the i^{th}digit for 32-bit signed binary integer. A more elegant approach is applying bitwise operators: XOR ,AND, and NOT.

We can use two integers one and two to represent the number of 1s on each bit digit. Meaning of one and two:

  • For each digit of one, 1 means True – it is one 1 and 0 means False – it is not one 1s.
  • For each digit of two, 1 means True – it is two 1 and 0 means False – it is not two 1s.

Let’s walk through it together with an example: [3,4,3,7,7,3,7].

After understanding what are one and two, let’s see how to implement it:

It seems un-readable, right? Don’t worry! Let me explain it a little bit.

  • one^nums[i] is to count 1s given a new number; & ~two is to deal with the cases when there are already two 1s.
  • two^nums[i] is to count 1s given a new number; & ~two is to deal with the cases when there are previously no 1s.

Feel free to leave a comment here!!

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments