645. Set Mismatch

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Example 2:

Input: nums = [1,1]
Output: [1,2]

Constraints:

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

Approach 1:

BruteForce

Iterate the list and for current value i , check if that is repeated value or not.

Finally you get the duplicate value. Find sum of all element from 1 to n using the formula (n*(n+1))/2 , let it be total1. Then find sum of list as total2

Then the missing number is total1-total2-dup.

Time: O(n²)

Space: O(1)

Approach 2:

Optimization over time complexity

Using hashmap

Store the count in hashmap. Then Iterate on hashmap to find duplicate while iterating XOR the key values called “xor_” . And XOR this value with number from 1 to n this will give the missing number as well ()

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        xor_=0
        miss,dup=0,0
        hash=dict()
        for i in range(len(nums)):
            if nums[i] not in hash:
                hash[nums[i]]=1
            else:
                hash[nums[i]]+=1
        cnt=1
        #cnt is number from 1 to len(nums)
        for i in hash:
            xor_^=i^cnt
            cnt+=1
            if(hash[i]==2):
                dup=i
        miss=xor_^cnt
        return[dup,miss]

Time: O(n)

Space: O(n)

Approach 3:

The same approach as 2 ,but we use set here to save some space

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        set_=set()
        result=[]
        xor_=0
        miss,dup=0,0
        for i in nums:
            set_.add(i)
            
        for i in range(len(nums)):
            xor_^=(i+1)^nums[i]
            
        for i in range(1,len(nums)+1):
            if(i not in set_):
                miss=i
        dup=miss^xor_    
        return([dup,miss])

Approach 4:

Optimize the time and space.

One of the best approach

Index based marking

As the numbers are from 1 to n and positive. We assume that index position (i-1)is allocated to number i . SO, for each number i we visit , we make nums[i-1] as negative. While traversing if value at a position is found to be negative then that is the duplicate number. And We iterate over the list again to see if any index position is not marked negative. Then that number is missing.

Time: O(n)

Space: O(1)

Approach 5:

Using XOR and bit manipulation

Another method is using the XOR operation and bit manipulation. Here XORING all the elements in the list from 1 to n elements and the given list give a result which is XOR of the missing and duplicate number. To identify the numbers from the result, we check which is the right most bit that is set in this result. We know, for that bit position to contain a ‘1’ in the final result, either of the missing or duplicate number(individual number in the result) must have a ‘1’ in the corresponding position, since it is a XOR operation. Thus we group the elements in the nums to 2 groups , such that one group contain all the numbers with that bit position containing a ‘1’ and other that containing ‘0’ at that bit position. We also include numbers from 1 to n , in these group accordingly based on them following this rule.

Finally we take XOR of these Group separately and also the result(which is XOR of the missing and duplicating number) we got earlier . So that they give missing and duplicating number from the result. But we don’t know which is the missing and duplicating number . So the final for loop.

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        xor_=0
        set_group_xor,unset_group_xor=0,0,
        for i in range(len(nums)):
            xor_^=(i+1)^nums[i]
        right=xor_ & ~(xor_-1)    
        for i in range(1,len(nums)+1):
            if(i&right!=0):
                set_group_xor^=i
            else:
                unset_group_xor^=i
            if(nums[i-1]&right!=0):
                set_group_xor^=nums[i-1]
            else:
                unset_group_xor^=nums[i-1]
                
                
        val1=xor_^set_group_xor
        val2=xor_^unset_group_xor
        for i in nums:
            if(i==val1):
                return(val1,val2)
        return(val2,val1)

Time: O(n)

Space: O(1)