[Leetcode] 137. Single Number II

https://leetcode.com/problems/single-number-ii/?envType=study-plan-v2&envId=top-interview-150

initial

So my bit is very weak. Revisit this logic of checking ith bit and setting ith bit.

https://velog.io/@whitehousechef/Bitmask

lets say this. But its all about modulo 3 where if we add up 3 equivalent numbers, that sum modulo 3 is 0. But if theres 1 unique value, that value modulo 3 still has that value as a remainder. Look at below example

We have our input numbers: [A, B, C, D, E, F, G]
Let's say A, B, C are the numbers X (appearing 3 times).
Let's say D, E, F are the numbers Y (appearing 3 times).
Let G be the unique number Z (appearing 1 time).

We are not looking at how X votes "yes" or "no" for different features. We are looking at how the same bit position (e.g., the 0th bit) contributes across all numbers.

Let's extract the value of the 0th bit from each number:

• bit_0_of_A
• bit_0_of_B
• bit_0_of_C
• bit_0_of_D
• bit_0_of_E
• bit_0_of_F
• bit_0_of_G

The bit_sum for the 0th position is:
bit_sum = bit_0_of_A + bit_0_of_B + bit_0_of_C + bit_0_of_D + bit_0_of_E + bit_0_of_F + bit_0_of_G

Now, consider the values bit_0_of_A, bit_0_of_B, bit_0_of_C. Since A, B, C are all the same number X, it means their 0th bit must be the same.
So, bit_0_of_A = bit_0_of_X
bit_0_of_B = bit_0_of_X
bit_0_of_C = bit_0_of_X

Their contribution to bit_sum is bit_0_of_X + bit_0_of_X + bit_0_of_X = 3 * bit_0_of_X.

Similarly, for D, E, F (which are all Y):
Their contribution to bit_sum is 3 * bit_0_of_Y.

And for G (the unique number Z):
Its contribution is 1 * bit_0_of_Z.

So, the total bit_sum for this position is:
bit_sum = (3 * bit_0_of_X) + (3 * bit_0_of_Y) + ... (for all numbers appearing 3 times) + (1 * bit_0_of_Z)

Now, apply modulo 3 to this sum:

bit_sum % 3 = ( (3 * bit_0_of_X) % 3 + (3 * bit_0_of_Y) % 3 + ... + (1 * bit_0_of_Z) % 3 ) % 3

• Since (3 * anything) % 3 is always 0, all terms from numbers appearing three times will become 0.

  • (3 * bit_0_of_X) % 3 = 0
  • (3 * bit_0_of_Y) % 3 = 0
  • etc.

• The only term that remains is from the unique number Z:

  • (1 * bit_0_of_Z) % 3 = bit_0_of_Z % 3
  • Since bit_0_of_Z can only be 0 or 1:
    • If bit_0_of_Z is 0, then 0 % 3 = 0.
    • If bit_0_of_Z is 1, then 1 % 3 = 1.

Therefore, bit_sum % 3 will directly give you the value of that bit (0 or 1) in the unique number Z.

Crucial Insight: It's not about individuals having different votes (like 2 "yes" and 1 "no"). It's about every instance of the same number having the exact same binary representation, and thus contributing the exact same bit value at a given position. When that bit value is added three times, its contribution to the sum modulo 3 is always zero, allowing the unique number's bit to shine through.

sol

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans=0
        for i in range(64):
            bitSum=0
            for num in nums:
                if (num>>i) & 1:
                    bitSum+=1
            if bitSum%3!=0:
                ans |= (1<<i)
                # Check if the 63rd bit is set (i.e., if ans is representing a negative number)
        # 1 << 63 creates a mask with only the 63rd bit set.
        if (ans & (1 << 63)) != 0:
            # If the 63rd bit is 1, subtract 2^64 to get the correct negative value.
            # This effectively converts the unsigned 64-bit interpretation to signed.
            ans -= (1 << 64)
        return ans

complexity

outer loop is constant but we iterate n in inner loop so
n time
1 space
the bot operations are all constant time