Friday, October 30, 2020

Find two elements that appear only once in array

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