Single Number


in 1st approach , there is no need for maintaining
no_duplicate_list
as 2 for loops can be run to check if num is in the array again. So it is O(n^n) time complexity and O(1) space complexity, this is to be further improved by hashing the values in array thus leading to O(n) time and O(n) space, as done in the 2nd approach.There is always an equal time gain at the cost of space I believe.

class Solution { public int singleNumber(int[] nums) { int result = 1; Set<Integer> set = new HashSet(); for(int num: nums) { if (set.contains(num)) { set.remove(num); } else { set.add(num); } } for(Integer elem: set) { result = elem; } return result; } }
Time Complexity: O(n*1) = O(n)
Space Complexity: O(n)

class Solution {
public int singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++){
if(set.contains(nums[i])){
set.remove(nums[i]);
}
else{
set.add(nums[i]);
}
}
int result = 0;
Iterator<Integer> it = set.iterator();
while(it.hasNext()){
result = it.next();
}
return result;
}
}

def singleNumber(self, nums): """ This code should be able to handle any size of number, any size of array so long as you can swap numbers reasonably, uses O(1) space, and runs in O(n). It's a modification of the kth element algo. (selection algo.). Also, it's such a pain to program this on the fly...tell me what you think. :type nums: List[int] :rtype: int """ import random def partition(nums, l, r): # use random to avoid dups for pivot (especially required when we get the highest or lowest number and we get stuck in inf loop) ri = random.randint(l, r) nums[r], nums[ri] = nums[ri], nums[r] p = nums[r] j = l # first greater than p offset for i in range(l, r): if nums[i] <= p: nums[j], nums[i] = nums[i], nums[j] if nums[j] == p: nums[l], nums[j] = nums[j], nums[l] j+=1 nums[r], nums[j] = nums[j], nums[r] # put the pivot in the position j (which is the leftmost number which is > p) return j # j is the partition's pivot offset def run(nums, l, r): if l==r: return nums[l] else: p = partition(nums, l, r) # p is last <= nums[p] value if (r  p) % 2 == 1: # if the right side has an odd number of nums, the odd one out is there return run(nums, p+1, r) else: return run(nums, l, p) return run(nums, 0, len(nums)1)

The prompt for this problem is somewhat misleading.
"Given an array of integers, every element appears twice except for one. Find that single one." Here, I could understand this sentence as the exception integer appears more than twice (or only once as the solution seems to assume here) However, if the exception integer appears more than twice, Approach #3 is not working.