# A general way to solve this kind of problem using 3-way partition (without bit operations) in C++

• To avoid bit operations, one can use 3-way partition as a solution. (with O(n) in average)
Constant space. The algorithm will modify the array in place.
The idea is to split the array in three part using a pivot (<pivot, =pivot, >pivot), and the single must be in one of the three parts, indicated by the remainder by 3 (or 4,5,6, etc.) being 1 while the other two parts have remainders by 3 being 0.

``````class Solution {
public:
int singleNumber(vector<int>& nums) {
int l = 0, r = nums.size()-1;
while (l < r) {
// in order to get a more reliable O(n)
// one should choose a random position
int pivot = nums[(l+r)/2];
int lower = l, middle = l, upper = r;
// swap in order to make:
// - lhs: nums[l..lower-1] < pivot
// - mid: nums[lower..middle-1] == pivot
// - rhs: nums[middle..r] > pivot
while (middle <= upper) {
if (nums[middle] < pivot)
std::swap(nums[lower++], nums[middle++]);
else if (nums[middle] > pivot)
std::swap(nums[middle], nums[upper--]);
else
++middle;
}
int lhs = lower - l;
// int mid = middle - lower;
int rhs = r - middle + 1;
if (lhs % 3 == 1) // if single is in lhs
r = lower-1;
else if (rhs % 3 == 1) // if single is in rhs
l = middle;
else { // else, it's in mid
l = lower;
r = middle - 1;
}
}
return nums[l];
}
};`````````

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