Repeat & Missing Number
XOR Approachpublic 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