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:
Initialize a variable
ans
to 0. This variable will eventually hold the unique number.-
Iterate through each element
nums[i]
in the input array:- XOR the current value of
ans
withnums[i]
and updateans
.
- XOR the current value of
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)
Top comments (0)