Single Number 1

Given an array of nums of n integers. Every integer in the array appears twice except one integer. Find the number that appeared once in the array.

Examples:
// Input : nums = [1, 2, 2, 4, 3, 1, 4]

// Output : 3

// Explanation : The integer 3 has appeared only once.

// Input : nums = [5]

// Output : 5

// Explanation : The integer 5 has appeared only once.

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {
        int x = 0;
        for (int n : nums)
            x ^= n;
        return x;
    }
};

Single Number 2

Given an array nums where each integer in nums appears thrice except one. Find out the number that has appeared only once.

 Examples:
// Input : nums = [2, 2, 2, 3]

// Output : 3

// Explanation : The integers 3 has appeared only once.

// Input : nums = [1, 0, 3, 0, 1, 1, 3, 3, 10, 0]

// Output : 10

// Explanation : The integers 10 has appeared only once.

1. Brute Force - store freq of  each element, return the one with freq 1 (TC: O(n), SC: O(n))
2. Better Approach 1 - for every bit index if (cnt % 3 == 1) then set that bit in the answer because For elements appearing three times, the bit count will be a multiple of three. The unique element's bit will not follow this pattern, using which it could be identified. TC: O(32 * n) = O(n)

int singleNumber(vector<int> &nums)
    {
        int x = 0;
        int ans = 0;
        for (int bitIndex = 0; bitIndex < 32; bitIndex++)
        {
            int cnt = 0;
            for (int n : nums)
            {
                if (n & (1 << bitIndex))
                    cnt++;
            }
            if (cnt % 3 == 1)
                ans |= (1 << bitIndex);
        }
        return ans;
    }

1. Better Approach 2 - Sort and make buckets of 3, check each bucket . TC: O(nlogn)

int singleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i += 3) {
            if (nums[i] != nums[i - 1]) {
                return nums[i - 1];
            }
        }
        
        /* If not found till now, then 
        the last number will be single */
        return nums[n - 1];
    }

1. Optimal - use buckets of ones and twos

 int singleNumber(vector<int>& nums) {        
        int ones=0,twos=0;

        for(int n:nums){
            ones=(ones^n)&~twos;
            twos=(twos^n)&~ones;
        }

        return ones;
    }

Single Number 3

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

/ Example:

// Input: nums = [1,2,1,3,2,5]
// Output: [3,5]
// Explanation:  [5, 3] is also a valid answer.

// Input: nums = [-1,0]
// Output: [-1,0]
// Example 3:

// Input: nums = [0,1]
// Output: [1,0]

//Approach:
// 1. Calculate the XOR of all elements in the array, which gives us the XOR of the two unique numbers.
// 2. Find a bit that is set in the XOR result(here we use the rightmost set bit).
// 3. Partition the numbers into two groups based on whether they have that rightmost set bit set or not.
// 4. XOR the numbers in each group to find the two unique numbers.
// Time Complexity: O(n), where n is the number of elements in the input array.
// Space Complexity: O(1), since we are using only a constant amount of extra space.