Single Number Ii

                                            
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        
        return ones;
    }
};

                                            
class Solution {
    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;
        
        for (int num : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }
        
        return seenOnce;
    }
}

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

                                            
int singleNumber(int* nums, int numsSize) {
    int ones = 0, twos = 0, common_bits;
    for (int i = 0; i < numsSize; i++) {
        twos |= (ones & nums[i]);
        ones ^= nums[i];
        common_bits = ones & twos;
        ones &= ~common_bits;
        twos &= ~common_bits;
    }
    return ones;
}

                                            
public class Solution {
    public int SingleNumber(int[] nums) {
        int ones = 0, twos = 0;
        
        foreach (int num in nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        
        return ones;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let ones = 0, twos = 0;
    
    for (let num of nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    
    return ones;
};

                                            
function singleNumber(nums: number[]): number {
    let ones = 0, twos = 0;
    
    for (let num of nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    
    return ones;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function singleNumber($nums) {
        $ones = 0;
        $twos = 0;
        
        foreach ($nums as $num) {
            $ones = (~$twos) & ($ones ^ $num);
            $twos = (~$ones) & ($twos ^ $num);
        }
        
        return $ones;
    }
}

                                            
class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var seenOnce = 0
        var seenTwice = 0
        
        for num in nums {
            seenOnce = ~seenTwice & (seenOnce ^ num)
            seenTwice = ~seenOnce & (seenTwice ^ num)
        }
        
        return seenOnce
    }
}

                                            
class Solution {
    fun singleNumber(nums: IntArray): Int {
        var seenOnce = 0
        var seenTwice = 0
        for (num in nums) {
            seenOnce = seenOnce xor num and seenTwice.inv()
            seenTwice = seenTwice xor num and seenOnce.inv()
        }
        return seenOnce
    }
}

                                            
class Solution {
  int singleNumber(List<int> nums) {
    int ones = 0, twos = 0;
    
    for (int num in nums) {
      ones = (ones ^ num) & ~twos;
      twos = (twos ^ num) & ~ones;
    }
    
    return ones;
  }
}

                                            
func singleNumber(nums []int) int {
    ones, twos := 0, 0
    for _, num := range nums {
        ones = (ones ^ num) & ^twos
        twos = (twos ^ num) & ^ones
    }
    return ones
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)
    ones = 0
    twos = 0
    
    nums.each do |num|
        ones = (ones ^ num) & (~twos)
        twos = (twos ^ num) & (~ones)
    end
    
    return ones
end

                                            
object Solution {
    def singleNumber(nums: Array[Int]): Int = {
        var ones = 0
        var twos = 0
        nums.foreach { num =>
            ones = (ones ^ num) & ~twos
            twos = (twos ^ num) & ~ones
        }
        ones
    }
}

                                            
impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let mut ones = 0;
        let mut twos = 0;
        for num in nums {
            ones = (ones ^ num) & !twos;
            twos = (twos ^ num) & !ones;
        }
        ones
    }
}

                                            
(define/contract (single-number nums)
  (-> (listof exact-integer?) exact-integer?)
  (cond
    [(= (length nums) 1) (car nums)]
    [else
     (let loop ([nums nums] [seen '()] [seen-twice '()])
       (cond
         [(null? nums) (car seen)]
         [(member (car nums) seen-twice)
          (loop (cdr nums) (remove (car nums) seen) (remove (car nums) seen-twice))]
         [(member (car nums) seen)
          (loop (cdr nums) seen (cons (car nums) seen-twice))]
         [else
          (loop (cdr nums) (cons (car nums) seen) seen-twice)]
         ))]))

                                            
defmodule Solution do
  @spec single_number(nums :: [integer]) :: integer
  def single_number(nums) do
    Enum.reduce(nums, %{}, fn x, acc ->
      Map.update(acc, x, 1, &(&1 + 1))
    end)
    |> Enum.find(fn {_key, value} -> value == 1 end)
    |> elem(0)
  end
end

To solve this coding challenge, we need to find an element in the given integer array

nums

that appears exactly once, while every other element appears three times. We need an approach that operates with linear runtime complexity (O(n)) and uses only constant extra space (O(1)).

# Explanation

The problem asks for a solution that works efficiently and using constant space. A very effective way to approach problems where elements repeat a specific number of times is using bitwise operations. Bitwise operations allow us to manipulate individual bits of numbers directly and are typically very fast. The core idea behind the solution is using two variables to track the count bits for the numbers seen so far. Here's how it works step-by-step:

Initialization : We start by initializing two variables,
ones

and
twos

, to zero. These will help us track bits that have appeared once and twice respectively.
Iterating Through the Array : We iterate through each number in the array and update the
ones

and
twos

variables based on the number.
Bitwise Operations :

ones

is updated to track bits where we have seen the bit appear an odd number of times. This includes the first and third time.
twos

is updated to track bits where we have seen the bit appear twice.

Clearing the Bits : After updating
ones

and
twos

, we need to clear bits that appear in both
ones

and
twos

. This is because such bits correspond to numbers that have appeared three times.
Returning the Result : By the end of the iteration,
ones

will hold the bit representation of the number that appears exactly once.

# Detailed Steps in Pseudocode

Initialize
ones

and
twos

to zero.
Iterate through each number in the array.

Compute
new_ones

to track bits that have appeared an odd number of times.
Compute
new_twos

to track bits that have appeared twice.
Update
ones

to be the new value of
new_ones

.
Update
twos

to be the new value of
new_twos

.

Clear bits from
ones

and
twos

when a bit appears in both.
Return
ones

, which contains the number that appears exactly once.

Here’s the complete pseudocode for the solution with comments:

                                            
# Pseudocode for finding the single number that appears exactly once

# Initialize two variables to store counts of bits appearing once and twice
ones = 0
twos = 0

# Iterate through each number in the input array nums
for num in nums:
# Update ones to include the current num only if it has not been included twice
new_ones = (ones ^ num) & ~twos

# Update twos to include the current num only if it has not been included once
new_twos = (twos ^ num) & ~new_ones

# Assign the new values to ones and twos for the next iteration
ones = new_ones
twos = new_twos

# The number that appears exactly once will be in ones
return ones

# Step-by-Step Explanation of the Pseudocode

Initialization :

ones = 0
twos = 0

Loop through each number :

For each number, update
new_ones

using bitwise XOR and AND operations:

(ones ^ num)

computes the XOR of
ones

and
num

, flipping bits where
num

has 1.
~twos

computes the bitwise complement of
twos

, ensuring that only bits not already in
twos

are affected.
The result is the new candidate for the bits in
ones

.

Update
new_twos

similarly:

(twos ^ num)

computes the XOR of
twos

and
num

, flipping bits where
num

has 1.
~new_ones

ensures that bits already in
ones

are not included.

Assign
new_ones

to
ones

, and
new_twos

to
twos

.

Result after loop :

After all iterations,
ones

will exclusively hold the bits of the number that appears once.

By following these detailed steps, you should be able to implement a solution that correctly identifies the single unique number in a list where every other number appears three times, efficiently and with constant space complexity.