This post is completed by 10 users
|Add to List|
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 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
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:
- Initialize a variable called "result" to 0.
- Iterate through each element in both arrays simultaneously.
- Perform an XOR operation between the current elements from arrA and arrB.
- Update the "result" variable by XOR-ing it with the current XOR result.
- Once the iteration is complete, the "result" variable will contain the extra element.
- Let's examine the implementation of the XOR logic:
Array A: [3, 4, 5, 2, 9, 6] Array B: [4, 3, 2, 9, 5, 7, 6] Extra Element: 7
- All elements appears thrice and one element appears once. Find that element in O(n) time and O(1) space Hard