## DEV Community is a community of 767,158 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

CodeWithML

Posted on • Updated on

# Find missing element from given two arrays.

### Problem Statement: Write a function to find the missing element from given two arrays.

#### Test Cases:

• [1, 2, 3, 4, 5, 6, 7],[3, 7, 2, 1, 4, 6] --> 5
• [5, 7, 7, 5, 7], [7, 7 ,5, 5] --> 7
• [9, 8, 7, 6, 5, 4, 3, 2, 1],[9, 8, 7, 5, 4, 3, 2, 1] --> 6
• [1, 2, 4, 7, 9], [7, 9, 4, 2] --> 1

There are number of ways this problem can be solved, below are 4 possible solutions

### Algorithm

1. Dictionary Method

• Initialise a dictionary.
• Iterate through the first array,
• If element at current iteration exists in dictionary,
• Increment it's value by 1.
• Else,
• Add the element as key and value as 1 in dictionary
• Iterate through the second array,
• If element at current iteration exists in dictionary,
• Decrement it's value by 1.
• Else,
• Add the element as key and value as 1 in dictionary.
• for every element in dictionary
• if value of the element is not 0
• return the element
2. Exclusive OR (XOR) Method

• Initialise variable result to 0
• Combine both the arrays.
• Iterate through the combined array
• Do XOR operation of every element with result
• Return the result, which will be the missing element
3. Sort Method

• Sort both the given arrays.
• Iterate over both the arrays simultaneously.
• At a given iteration if value of both the iterators are different,
• return the element from first array, as it is the missing element.
4. Sum Method

• Calculate the sum of all the elements in both the arrays.
• Subtract the sum of second array from the first array.
• The result will be the missing element.

### Time and Space complexity

1. Dictionary Method
• Time Complexity: O(n)
• Space Complexity: O(n)
2. XOR Method
• Time Complexity: O(n)
• Space Complexity: O(n)
3. Sort Method
• Time Complexity: O(nlogn)
• Space Complexity: O(n)
4. Sum Method
• Time Complexity: O(n)
• Space Complexity: O(1)

### Code

``````class MissingElement(object):
def missingElement(self, arr1, arr2):
count = {}
for element in arr1:
if element in count:
count[element] += 1
else:
count[element] = 1
for element in arr2:
if element in count:
count[element] -= 1
else:
count[element] = 1
for k in count:
if count[k] != 0:
return k

def missingElement2(self, arr1, arr2):
result = 0
for element in arr1 + arr2:
result ^= element
return result

def missingElement3(self, arr1, arr2):
arr1.sort()
arr2.sort()
for ele1, ele2 in zip(arr1, arr2):
if ele1 != ele2:
return ele1
return arr1[-1]

def missingElement4(self, arr1, arr2):
return abs(sum(arr1) - sum(arr2))
``````

### Unit Test

``````import unittest
from missingElement import MissingElement

class TestMisssingElement(unittest.TestCase):
def test_ele(self, sol):
self.assertEqual(sol([5, 5, 7, 7], [5, 7, 7]), 5)
self.assertEqual(sol([1, 2, 3, 4, 5, 6, 7],
[3, 7, 2, 1, 4, 6]), 5)
self.assertEqual(sol([9, 8, 7, 6, 5, 4, 3, 2, 1],
[9, 8, 7, 5, 4, 3, 2, 1]), 6)
print("All test cases passed")

def main():
test = TestMisssingElement()
element = MissingElement()
test.test_ele(element.missingElement)
test.test_ele(element.missingElement2)
test.test_ele(element.missingElement3)
test.test_ele(element.missingElement4)

if __name__ == "__main__":
main()
``````

Github repo

Original article