# C++ program, Space O(1), Time O(N), bit search

• Notice the fact that in an array 1...n, the number of even is always <= n/2

if the number of even in the given array >= n/2, then the duplicate number must be a even number. Otherwise, the duplicate is a odd number.

We could get the duplicate number bit by bit according to the aforementioned method.

``````class Solution {
public:
int findDuplicate(vector<int>& nums) {
int len=nums.size();
int n=len-1;
int zeros=0;
int ones=0;
int result=0;
int taillong=0;
for(int i=0;i<32;i++){ //bit by bit
for(int i=0;i<len;i++){
// Discard useless numbers
if((nums[i]&((1<<taillong)-1))==result){ //last taillong bits equal result
if(((nums[i]>>taillong)&0x01)==0) zeros++;
else ones++;
}
}
if(n/2<zeros){
taillong++;
n=zeros;
}else{
result+=(1<<taillong);
taillong++;
n=ones;
}
ones=zeros=0;
}
return result;
}
};``````

• Good idea, your code can be accepted, but will fail for one of the following cases:
[1,2,3,4,5,6,4]
[1,2,3,4,5,6,7,8,9,5]

leetcode should add these test cases to the judge system.

• ``````class Solution {
public:
// [1,2,3,4,5,6,4]
// [1,2,3,4,5,6,7,8,9,5]
int findDuplicate(vector<int>& nums) {
int zeroCnt = 0, oneCnt = 0, bit0 = 0;
int ans = 0;
// decide duplicate bit from 0 to 32
for(int i = 0; i < 8*sizeof(int); ++i){
zeroCnt = 0;
oneCnt = 0;
for(int j = 0; j < nums.size(); ++j){
if((nums[j] & ((1 << i) - 1)) == ans){
// [0, i - 1] bits equal to ans
if(((nums[j] >> i) & 1) == 0){
++zeroCnt;
}else{
++oneCnt;
}
}
}

// !NOTE: [1, n] not [0, n]
if((bit0 == 0 && oneCnt > zeroCnt) || (bit0 == 1 && oneCnt >= zeroCnt)){
ans |= (1 << i);
}

if(i == 0){
bit0 = ans & 1;
}
}

return ans;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.