# 3 Accepted Solutions: bit-wise inverse, swap, and cheat(using O(n) space)

• The cheating one is the most straight forward; I tested it just to see if the problem's author meant to allow the additional space usage; And the answer is (currently?) yes, if the author is not mistaking. It is accepted even when using integer vector as presentation records.

Okay, let's talk about the real one:

1. the first one is recording if a number is presented in the array or not. Taking advantage of the problem input constraint, there are only positive integers. When a number is inverted at bit-level, we can tell the original number as well as if the number is inverted. Some other reversible operations can be used as well: simple negation, or add the array size. I like bitwise inverse because it is the simplest one in terms of implementation effort and hardware complexity. Oh, and inverse has the highest flexibility: negation only covers "positive" integers" instead of "non-negative" ones, and size offest needs to handle overflow issue carefully.

2. Swap-based approach is to put number 'x' into position 'x-1'. When there is a collision, then we know the number is repeated. (I like to make my thinking clean and I make the position shift outside the loop (see declaration of 'int* arr'), so you won't see that coming in the loop body. )

``````class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {

int sz = nums.size()+1;
vector<int> ret;
#define CHEAT // on space
#ifdef CHEAT
bool presented[sz] = {};
/* using either of the following 2 array forms is still accepted
char presented[sz] = {};
vector<int> presented(sz);
*/
for(int x : nums) {
if(presented[x]) ret.push_back(x);
else presented[x] = true;
}
#elif 0 //using bitwise inverse
for(int i=1;i<sz;++i) {
int n = max(arr[i],~arr[i]);
if(arr[n] < 0) ret.push_back(n);
else arr[n] = ~arr[n];
}
#else //swap based
int* arr = nums.data()-1;
for(int i=1;i<sz;) {
if(!arr[i] || arr[i] == i) {
++i;
} else if(arr[i] == arr[arr[i]]) {
ret.push_back(arr[i]);
arr[i] = arr[arr[i]] = 0; // remove the number by setting zero
++i;
} else {
swap(arr[i],arr[arr[i]]);
}
}
#endif
return ret;
}
};
``````

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