27282930313233343536373839404142434445464748495051

package main

import (
    "fmt"
    "sort"
)

/* Function to get the single 
number in the given array */
func singleNumber(nums []int) []int {
    // Array to store the answer
    var ans []int

    /* Map to store the elements 
    and their frequencies */
    mpp := make(map[int]int)

    // Iterate on the array
    for i := 0; i < len(nums); i++ {
        mpp[nums[i]]++ // Update the map
    }

    // Iterate on the map
    for key, val := range mpp {
        // If frequency is 1
        if val == 1 {
            /* Add the element to
            the result array */
            ans = append(ans, key)
        }
    }

    // Return the result after sorting
    sort.Ints(ans) // sort the slice in increasing order
    return ans
}

func main() {
    nums := []int{1, 2, 1, 3, 5, 2}

    /* Creating an instance of 
    Solution class */
    // (In Go, call the function directly)

    /* Function call to get the single 
    number in the given array */
    ans := singleNumber(nums)

    fmt.Printf("The single numbers in given array are: %d and %d\n", ans[0], ans[1])
}

Complexity Analysis:

Time Complexity: O(N) (where N is the size of the array)

Traversing the array to update the Hash Map - O(N).

Traversing on the map - O(N) (in worst case).

Sorting the answer array - O(2*log(2)) ~ O(1).
Hence, O(N) + O(N) + O(1) ~ O(N).

Space Complexity: O(N), Using a hashmap data structure and in the worst-case (when all elements in the array are unique), it will store N key-value pairs.

1d:T57c7,

Intuition:

An optimal approach to solve this problem will be possible if we can divide the elements in array into two groups such that each group only contains one unique element. This way, the problem boils down to Single Number-I and both the unique elements can be identified with ease.

Now, to divide the numbers into two groups(buckets), the rightmost set bit in the overall XOR of all elements can be used. The overall XOR of all elements is equivalent to the XOR of the two unique numbers.

Why Divide using the Rightmost Set Bit?

This is because of the following reasons:

The two unique numbers needs to be separated into two different groups, and the rightmost set bit in the overall XOR will indicate the bit position where the the two unique numbers differ.
Using this bit, all the elements in the array can be divided into two groups (buckets):
- One group where this bit is set.
- Another group where this bit is not set.

Approach:

Traverse the entire array, performing an XOR operation on all numbers. This will effectively cancel out all the numbers that appear twice, leaving us with the XOR of the two unique numbers.
Determine the rightmost set bit (bit that is 1) in the result from the first step. This set bit can be used to differentiate the two unique numbers since they must differ at this bit position.
Traverse the array again, but this time divide the numbers into two groups:
- One group where the numbers have the rightmost set bit.
- Another group where the numbers do not have this bit set.
- Perform XOR operations while adding numbers in each group. This will cancel