# Quicksort like solution

• I am not able to come up with the bit manipulation solution. They are really brilliant. Here is a quicksort like solution, which should be easier to come up with. The best case should be O(n).

``````public class Solution {
Random rand = new Random();

public int singleNumber(int[] nums) {
return helper(nums, 0, nums.length-1);
}

public int helper(int[] nums, int begin, int end){
if(begin > end) return -1;//UNFOUND; not possible in this problem.
if( begin == end) return nums[begin];
int pivotIndex =  rand.nextInt(end-begin+1)+begin;
swap(nums, pivotIndex, end);
int pivot = nums[end];
int p = begin;
for(int i = begin; i < end; i++){
if( nums[i] <= pivot){
swap(nums, i, p);
p++;
}
}
swap(nums, p, end);

if( (p - begin+1) % 3 != 0){
return helper(nums, begin, p);
}else{
return helper(nums, p+1, end);
}

}

public void swap(int[] nums, int i, int j){
if(i == j) return;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````

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