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);
}
}
}
sorry, I feel a little confused about this solution.
ReplyDeleteIf 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?