Missing Numbers

Sort by

recency

|

1251 Discussions

|

  • + 0 comments
    def missingNumbers(arr, brr):
        # Write your code here
        
        arr_freq = Counter(arr)
        brr_freq = Counter(brr)
        
        missing = []
        
        for key in brr_freq:
            if brr_freq[key] != arr_freq[key]:
                missing.append(key)
                
        return sorted(missing)
    
  • + 0 comments

    Time Complexity =

    def missingNumbers(arr:list, brr:list):
        sol = []
        
        arr_frequency = Frequency(arr)
        brr_frequency = Frequency(brr)
    
        for number , freq in brr_frequency.items():
            if number not in arr_frequency:
                sol.append(number)
            elif number in arr_frequency:
                if arr_frequency[number] != freq: 
                    sol.append(number)
        return sorted(sol)
    
    def Frequency(elements:list):
        temp = {}
        for element in elements:
            if element not in temp:
                temp[element] = 1
            else:
                temp[element] += 1
        return temp
    
  • + 0 comments

    Python 3 Solution

    • We need to find frequencies of elements of both arrays, and store somewhere like element1:frequency, element2:frequency i.e. dictionary or what we call Hash Map in Data Structures. -> This is O(n) operation
    • For every unique element in brr array, we need to check if its frequency count is greater than how many times it appear in arr array. Since dictionary has unique elements as well as freq counts, lets loop over its keys, and compare values with arr's freq count (dictionary values). If greater add it in result list. -> O(n) to loop, comparisons on dict are O(1)
    • sort the result list and return it. -> O(klogk) where k is unique missing elements which will be <= 100.
    • Overall time complexity is around O(n).
    def missingNumbers(arr, brr):
        missing = []
        arrcount = dict()
    		# calculate and store frequency counts for every arr element
        for a in arr:
            if arrcount.get(a):
                arrcount[a] += 1
            else:
                arrcount[a] = 1
    		
        brrcount = dict()
        for b in brr:
            if brrcount.get(b):
                brrcount[b] += 1
            else:
                brrcount[b] = 1
    						
        for key in brrcount:
            if brrcount[key]>arrcount.get(key,0):
                missing.append(key)
        return sorted(missing)
    
  • + 0 comments

    Kotlin

    fun missingNumbers(arr: Array<Int>, brr: Array<Int>): List<Int> {
        val countMap = brr.groupingBy { it }.eachCount().toMutableMap()
    
        arr.forEach { y ->
            countMap[y]?.let { count ->
                if (count > 1) countMap[y] = count - 1 else countMap.remove(y)
            }
        }
    
        return countMap.keys.sorted()
    }
    
  • + 0 comments

    python 3

    from collections import Counter
    
    def missingNumbers(arr, brr):
        org = Counter(brr)
        miss = Counter(arr)
        missing = []
        
        for num, count in org.items():
            if miss[num] < count:
                missing.append(num)
                
        return sorted(missing)