Problem: 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.
Example:
Input: nums = [1,2,1,3,2,4] Output: [3,4]
Approach: It is a simple problem. Can be easily understood by looking at the code.
Implementation in C#:
public int[] FindTwoNumbers(int[] nums)
{
if (nums?.Length <= 1)
{
return null;
}
if (nums.Length == 2)
{
return nums;
}
int[] result = new int[2];
int xor = 0;
// Say our target number are a and b. Xoring all the elements of array will produce a xor b
foreach(int num in nums)
{
xor ^= num;
}
// Right now xor will have a xor b
// Get the rightmost set bit, means the right most bit where a and b have different bits
int setBit = xor & ~(xor - 1);
// Now just take XOR separately based on above bit to get a and b
foreach (int num in nums)
{
if ((num & setBit) != 0)
{
result[0] ^= num;
}
else
{
result[1] ^= num;
}
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment