DAY 68 - Single Number I

Welcome to DAY 68. Today we will diverge once again into the Data Structures and look at some more questions. Today we are going to do a question again on Bit Manipulation.

Question: Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

We are going to solve this problem using Bit Manipulation
Incase you don't know what's bit manipulation, It is the modification or manipulation of smallest form of data(a bit) and using their properties with bit operators to generate favorable results.
Read the article before this for a start.

Intuition: Using XOR Operation

Associative Property of XOR: The XOR operation has the associative property, which means that (a ^ b) ^ c is equivalent to a ^ (b ^ c). This property allows us to combine numbers in any order without changing the result.

Cancelling Out Duplicates: When we XOR a number with itself, it results in 0. Additionally, XORing any number with 0 leaves the number unchanged. By XORing all numbers in the array together, the duplicate numbers will effectively cancel each other out, resulting in the unique number being left in the final XOR result.

Using these XOR properties, we will find out the ans.

Algorithm Steps:

1. Initialize a variable ans to 0. This variable will eventually hold the unique number.

2. Iterate through each element nums[i] in the input array:

   • XOR the current value of ans with nums[i] and update ans.

3. After the loop, the variable ans holds the unique number that appears only once in the array.

Example:

Input Array: [4, 2, 4, 3, 2]

• Initialize ans as 0.
• Iterate through the array:
  • ans ^= 4 -> ans becomes 4.
  • ans ^= 2 -> ans becomes 6.
  • ans ^= 4 -> ans becomes 2.
  • ans ^= 3 -> ans becomes 1.
  • ans ^= 2 -> ans becomes 3.

Final ans value is 3, the unique number in the array.

Code:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++)   
            ans = ans ^ nums[i];
        return ans;
    }
};

Complexity Analysis:

Time: O(N)
Space: O(1)