Repeat & Missing Number

XOR Approach
 avatar
unknown
java
6 days ago
1.2 kB
4
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};
    }
}
Leave a Comment