This post is completed by 13 users

  • 5
Add to List
Beginner

541. Find an extra element in two almost similar arrays

Given two arrays where the second array has all the elements from the first array and one extra element. 

Example: 

Example 1:
arrA = [1, 4, 2, 5, 7]
arrB = [1, 2, 4, 1, 7, 5]
Output: 1

Example 2:
arrA = [1, 8, 2, 0]
arrB = [1, 8, 4, 2, 0]
Output: 4

Solution:

Various approaches can be employed to solve this problem. However, an efficient solution involves utilizing the XOR operation. XOR, also known as exclusive OR, is a logical operation that returns true only when the operands differ. By exploiting this property, we can easily identify the extra element in an array. Remember A XOR A = 0 

To find the extra element using the XOR approach, follow these steps:

  1. Initialize a variable called "result" to 0.
  2. Iterate through each element in both arrays simultaneously.
  3. Perform an XOR operation between the current elements from arrA and arrB.
  4. Update the "result" variable by XOR-ing it with the current XOR result.
  5. Once the iteration is complete, the "result" variable will contain the extra element.
  6. Let's examine the implementation of the XOR logic:

Output:

Array A: [3, 4, 5, 2, 9, 6]
Array B: [4, 3, 2, 9, 5, 7, 6]
Extra Element: 7