# Time: O(n) # Space: O(1) # The set S originally contains numbers from 1 to n. # But unfortunately, due to the data error, one of the numbers # in the set got duplicated to another number in the set, which results # in repetition of one number and loss of another number. # # Given an array nums representing the data status of this set after the error. # Your task is to firstly find the number occurs twice and then find the number # that is missing. Return them in the form of an array. # # Example 1: # Input: nums = [1,2,2,4] # Output: [2,3] # Note: # The given array size will in the range [2, 10000]. # The given array's numbers won't have any order. class Solution(object): def findErrorNums(self, nums): """ :type nums: List[int] :rtype: List[int] """ x_xor_y = 0 for i in xrange(len(nums)): x_xor_y ^= nums[i] ^ (i+1) bit = x_xor_y & ~(x_xor_y-1) result = [0] * 2 for i, num in enumerate(nums): result[bool(num & bit)] ^= num result[bool((i+1) & bit)] ^= i+1 if result[0] not in nums: result[0], result[1] = result[1], result[0] return result # Time: O(n) # Space: O(1) class Solution2(object): def findErrorNums(self, nums): """ :type nums: List[int] :rtype: List[int] """ result = [0] * 2 for i in nums: if nums[abs(i)-1] < 0: result[0] = abs(i) else: nums[abs(i)-1] *= -1 for i in xrange(len(nums)): if nums[i] > 0: result[1] = i+1 else: nums[i] *= -1 return result # Time: O(n) # Space: O(1) class Solution3(object): def findErrorNums(self, nums): """ :type nums: List[int] :rtype: List[int] """ N = len(nums) x_minus_y = sum(nums) - N*(N+1)//2 x_plus_y = (sum(x*x for x in nums) - N*(N+1)*(2*N+1)/6) // x_minus_y return (x_plus_y+x_minus_y) // 2, (x_plus_y-x_minus_y) // 2