I was using the partition technique similar to what we have in Randomized Quick Sort.

The key idea is that **if there are 3k elements that is less than or equal to the pivot, then the single number must be larger than the pivot**, otherwise there would be 3k+1 elements.

Only that in quick sort we have T(n)=2T(n/2)+O(n).

Here we have T(n)=T(n/2)+O(n). Mathematically, it should be T(n)=O(n).

```
int partition(int *nums, int l, int r){
int i = l,j = l;
int t = l + rand()%(r-l+1);
int tmp,p;
p = nums[t];
nums[t] = nums[r];
nums[r] = p;
for ( ; i <= r; i++){
if (nums[i] <= p ){
tmp = nums[i];
nums[i] = nums[j];
nums[j++] = tmp;
}
}return j;
}
int singleNumber(int* nums, int numsSize) {
int i = 0, j = numsSize-1;
int par;
while(i<j){
par = partition(nums,i,j);
if (par%3 == 0){
i = par;
} else j = par-1;
}
return nums[i];
}
```