Created
June 13, 2017 17:42
-
-
Save anil477/2329becb82c33d8c419ccdba19350440 to your computer and use it in GitHub Desktop.
Find the two non-repeating elements in an array of repeating elements
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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