-
Notifications
You must be signed in to change notification settings - Fork 657
/
Copy pathmissingAndRepeatingNumberJava
57 lines (45 loc) · 1.57 KB
/
missingAndRepeatingNumberJava
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
static int x, y;
static void getTwoElements(int arr[], int n)
{
/* Will hold xor of all elements
and numbers from 1 to n */
int xor1;
/* Will have only single set bit of xor1 */
int set_bit_no;
int i;
x = 0;
y = 0;
xor1 = arr[0];
/* Get the xor of all array elements */
for (i = 1; i < n; i++)
xor1 = xor1 ^ arr[i];
/* XOR the previous result with numbers from
1 to n*/
for (i = 1; i <= n; i++)
xor1 = xor1 ^ i;
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor1 & ~(xor1 - 1);
/* Now divide elements into two sets by comparing
rightmost set bit of xor1 with the bit at the same
position in each element. Also, get XORs of two
sets. The two XORs are the output elements. The
following two for loops serve the purpose */
for (i = 0; i < n; i++) {
if ((arr[i] & set_bit_no) != 0)
/* arr[i] belongs to first set */
x = x ^ arr[i];
else
/* arr[i] belongs to second set*/
y = y ^ arr[i];
}
for (i = 1; i <= n; i++) {
if ((i & set_bit_no) != 0)
/* i belongs to first set */
x = x ^ i;
else
/* i belongs to second set*/
y = y ^ i;
}
// at last do a linear check which amont x and y is missing or repeating
/* *x and *y hold the desired output elements */
}