Challenges

Detailed Explanation

Objective:

We need to find the single number that appears exactly once in an array where every other number appears exactly three times.

Key Insight:

Using bitwise operations, we can track the occurrence of each bit across all numbers. By maintaining counters for bits that appear once and twice, we can effectively isolate the bits of the number that appears exactly once.

Bitwise Operations:

  1. ones: Tracks bits that have appeared once.

  2. twos: Tracks bits that have appeared twice.

Core Bitwise Formulas:

  • ones = (ones ^ num) & ~twos

    • Explanation:

      • ones ^ num: Adds the bits of num to ones if they are not already there, or removes them if they are.

      • & ~twos: Ensures that if a bit is already in twos, it is removed from ones. This keeps track of bits that have only appeared once but not yet twice.

  • twos = (twos ^ num) & ~ones

    • Explanation:

      • twos ^ num: Adds the bits of num to twos if they are not already there, or removes them if they are.

      • & ~ones: Ensures that if a bit is already in ones, it is removed from twos. This keeps track of bits that have appeared twice but not yet three times.

Step-by-Step Walkthrough:

Initialize:

  • ones = 0

  • twos = 0

Iterate through the array:

For each number num in the array, update ones and twos:

  1. First Occurrence of a Bit:

    • Suppose num = 5 (binary 0101).

    • Initially, ones = 0 and twos = 0.

    • Update:

      • ones = (ones ^ num) & ~twos

        • ones = (0 ^ 0101) & ~0000 = 0101 & 1111 = 0101

      • twos = (twos ^ num) & ~ones

        • twos = (0 ^ 0101) & ~0101 = 0101 & 1010 = 0000

  2. Second Occurrence of the Same Bit:

    • When num = 5 appears again:

    • Update:

      • ones = (ones ^ num) & ~twos

        • ones = (0101 ^ 0101) & ~0000 = 0000 & 1111 = 0000

      • twos = (twos ^ num) & ~ones

        • twos = (0000 ^ 0101) & ~0000 = 0101 & 1111 = 0101

  3. Third Occurrence of the Same Bit:

    • When num = 5 appears the third time:

    • Update:

      • ones = (ones ^ num) & ~twos

        • ones = (0000 ^ 0101) & ~0101 = 0101 & 1010 = 0000

      • twos = (twos ^ num) & ~ones

        • twos = (0101 ^ 0101) & ~0000 = 0000 & 1111 = 0000

At the end of this process, ones and twos are reset to 0 for any number that appears exactly three times.

Extract the Single Occurrence:

  • The bits of the number that appears exactly once will remain in ones since it won't be canceled out after three appearances.

  • Thus, after processing all numbers, ones will contain the single number.

Example:

Let's run through a full example with an array [2, 2, 3, 2]:

  1. Initialize: ones = 0, twos = 0

  2. First number 2 (binary 10):

    • ones = (0 ^ 10) & ~0 = 10

    • twos = (0 ^ 10) & ~10 = 0

  3. Second number 2 (binary 10):

    • ones = (10 ^ 10) & ~0 = 0

    • twos = (0 ^ 10) & ~0 = 10

  4. Third number 2 (binary 10):

    • ones = (0 ^ 10) & ~10 = 0

    • twos = (10 ^ 10) & ~0 = 0

  5. Fourth number 3 (binary 11):

    • ones = (0 ^ 11) & ~0 = 11

    • twos = (0 ^ 11) & ~11 = 0

Finally, ones = 3 which is the number that appears exactly once.

Code Implementation:

=> Remember this code

def singleNumber(nums):
    ones, twos = 0, 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

# Example usage:
nums = [2, 2, 3, 2]
print(singleNumber(nums))  # Output: 3

Summary:

This approach effectively uses bitwise operations to isolate the single occurrence of a number in an array where every other number appears three times. It works in linear time and uses constant space, making it an efficient solution to the problem.

PreviousBitwiseNextArray

Last updated