Skip to content

Instantly share code, notes, and snippets.

@anil477
Created June 13, 2017 17:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anil477/2329becb82c33d8c419ccdba19350440 to your computer and use it in GitHub Desktop.
Save anil477/2329becb82c33d8c419ccdba19350440 to your computer and use it in GitHub Desktop.
Find the two non-repeating elements in an array of repeating elements
/* Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way */
class RepeatElement
{
void printRepeating(int arr[], int size)
{
int xor = arr[0];
int set_bit_no;
int i;
int x = 0, y = 0;
for (i = 1; i < size; i++)
xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
set_bit_no = (xor & ~(xor - 1));
System.out.println("Set Bit " + set_bit_no);
for (i = 0; i < size; i++) {
int a = arr[i] & set_bit_no;
System.out.println( " arr[i] = " + arr[i] );
System.out.println( " a = " + a );
if (a != 0)
x = x ^ arr[i]; /*XOR of first set in arr[] */
else
y = y ^ arr[i]; /*XOR of second set in arr[] */
}
System.out.println("The two reppeated elements are :");
System.out.println(x + " " + y);
}
public static void main(String[] args)
{
RepeatElement repeat = new RepeatElement();
int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
int arr_size = arr.length;
repeat.printRepeating(arr, arr_size);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment