Interview Question Categories

FIND 2 ODD OCCURING INTS IN AN ARRAY

FIND 2 ODD OCCURING INTS IN AN ARRAY
namespace Find2OddOccuringIntsinanArray
{
    class Program
    {
        public static void Find2OddOccuringInts(int[] Arr)
        {
            int OddOccurence = 0;

            for (int i = 0; i < Arr.Length; i++)
            {
                OddOccurence ^= Arr[i];
            }

            //Now variable Oddoccurences will contain 
            //information about 2 odd occuring numbers.
            //In the variable Oddoccurences only those bits 
            //will be set in which the 2 odd occuring numbers differ.


            //Now get the Least significant bit set in the variable OddOccurences.

            OddOccurence = OddOccurence & -(OddOccurence);

            //Use the above OddOccurences variable to divide 
            //the array, those with that least significant bit set and those not.
            int x=0, y=0;
            for (int i = 0; i < Arr.Length; i++)
            {
                if ((Arr[i] & OddOccurence) > 0)
                {
                    x = x ^ Arr[i];
                }
                else
                {
                    y = y ^ Arr[i];
                }
            }

            Console.WriteLine(x + "   " + y);
        }

        static void Main(string[] args)
        {
            int[] Arr = { 1, 3, 4, 5, 1, 5, 6, 6, 7, 8, 7, 8 };
            Find2OddOccuringInts(Arr);
        }
    }
}

1 comment:

  1. sorry, I feel a little confused about this solution.
    If the two odd occurrence numbers are same in the least significant bit, which means the OddOccurence variable will be 0 after you & with its negative. Then those two numbers & OddOccurence will be both > 0 (if they are all 0 in the end bit) or < 0 (if they are all 1 in the end bit). So how could you figure out those two numbers?

    ReplyDelete