Repeat & Missing Number
XOR Approachunknown
java
a year ago
1.2 kB
11
Indexable
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
public int[] repeatedNumber(final int[] A) {
int xor = 0, i, n = A.length, idx = 0, set = 0, unset = 0, c = 0;
for(i=0;i<n;++i) // we will get the xor of repeated number and missing number
{
xor ^= A[i];
xor ^= (i+1);
}
for(i=0;i<32;++i) // find the first set bit
{
if((xor & (1<<i)) > 0)
{
idx = i;
break;
}
}
for(i=0;i<n;++i) // group the numbers as set, unset
{
if((A[i] & (1<<idx)) > 0)
set ^= A[i];
else
unset ^= A[i];
}
for(i=1;i<=n;++i)
{
if((i & (1<<idx)) > 0)
set ^= i;
else
unset ^= i;
}
for(i=0;i<n;++i)
{
if(A[i]==set)
c++;
}
return (c==2)?new int[]{set, unset}:new int[]{unset, set};
}
}
Editor is loading...
Leave a Comment