C Program to find the two elements present only one time while other elements are present two times - Bit Manipulation

 

// Program by Akash Tripathi (@proakash256) 

 

// In an Integer Array, all the Numbers

// are present two times except two

// Elements. Find both Integers in O(n)

// time complexity and O(1) Space

// Complexity.

// 0 ^ n = n

// n ^ n = 0

#include <stdio.h>

int main()

{

    int n, a = 0, b = 0, result = 0 , set_bit;

    printf("Enter the number of elements

            you want to enter : ");

    scanf("%d", &n);

    int ar[n];

    printf("\nEnter the Elements :\n");

    for (int i = 0; i < n; i = i + 1)

        scanf("%d", &ar[i]);

    for (int i = 0; i < n; i = i + 1)

    {

        result = result ^ ar[i];

    }

    // To get the rightmost set bit

    set_bit = result & (~result + 1);

    /* Dividing the elements in two sets by

    comparing rightmost set bit of result

with bit at same position in each

element. */

    for (int i = 0; i < n; i = i + 1)

    {

        if ((ar[i] & set_bit) > 0)

        {

            a = a ^ ar[i];

        }

        else

        {

            b = b ^ ar[i];

        }

    }

    printf("\nFirst Element is %d.", a);

    printf("\nSecond Element is %d.", b);

    return 0;

}