Searching: Find index of an extra element in a sorted array

Problem Statement:

You are given 2 sorted arrays.

There is only 1 element difference between the arrays.

You need to find the extra element index.

Example:

Input:

a = [1, 2, 3, 4, 5, 6, 7, 8]

b = [1, 3, 4, 5, 6, 7, 8]

Output:

1

The extra element is 2 in array a.

Its index is 1.

Solution 1:

Traverse the array

Check if the ith element is same in both of the arrays

If the element is not similar, then print the index.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Binary Search

Create a variable result equal to the size of the array.

Then use binary search, run till all the index greater than or equal to the index of the missing element.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

int solution_1 (int arr1[],  int arr2[], int n)
{
for (int i = 0; i < n; i++)
	if (arr1[i] != arr2[i])
		return i;

return n;
}

int solution_2 (int arr1[], 
              int arr2[], int n)
{
    int result = n; 
    int left = 0, right = n - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (arr2[mid] == arr1[mid])
            left = mid + 1;
 
        else
        {
            result = mid;
            right = mid - 1;
        }
    }
 

    return result;
}


int main()
{
	int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8};
	int arr2[] = {1, 3, 4, 5, 6, 7, 8};

	int n = sizeof(arr2) / sizeof(arr2[0]);

	cout << solution_1(arr1, arr2, n)<<endl;
	cout << solution_2(arr1, arr2, n)<<endl;
	return 0;
}

Output

1
1