# Find index of an extra element present in one sorted array

Given two sorted arrays. There is only 1 difference between the arrays. First array has one element extra added in between. Find the index of the extra element.

Examples :

Input : {2, 4, 6, 8, 9, 10, 12};
{2, 4, 6, 8, 10, 12};
Output : 4
The first array has an extra element 9.
The extra element is present at index 4.

Input :  {3, 5, 7, 9, 11, 13}
{3, 5, 7, 11, 13}
Output :  3

Method 1 (Basic)

The basic method is to iterate through the whole second array and check element by element if they are different.

## C++

 // C++ program to find an extra  // element present in arr1[] #include using namespace std;    // Returns index of extra element  // in arr1[]. n is size of arr2[].  // Size of arr1[] is n-1. int findExtra(int arr1[],                int arr2[], int n) { for (int i = 0; i < n; i++)     if (arr1[i] != arr2[i])         return i;    return n; }    // Driver code int main() {     int arr1[] = {2, 4, 6, 8,                    10, 12, 13};     int arr2[] = {2, 4, 6,                    8, 10, 12};     int n = sizeof(arr2) / sizeof(arr2[0]);        // Solve is passed both arrays     cout << findExtra(arr1, arr2, n);     return 0; }

## Java

 // Java program to find an extra  // element present in arr1[] class GFG  {        // Returns index of extra element      // in arr1[]. n is size of arr2[].      // Size of arr1[] is n-1.     static int findExtra(int arr1[],                           int arr2[], int n)     {     for (int i = 0; i < n; i++)         if (arr1[i] != arr2[i])             return i;            return n;     }            // Driver Code     public static void main (String[] args)     {         int arr1[] = {2, 4, 6, 8,                        10, 12, 13};         int arr2[] = {2, 4, 6,                        8, 10, 12};         int n = arr2.length;                // Solve is passed both arrays         System.out.println(findExtra(arr1,                                       arr2, n));     } }    // This code is contributed by Harsh Agarwal

/div>

## Python3

 # Python 3 program to find an  # extra element present in arr1[]       # Returns index of extra . # element in arr1[] n is  # size of arr2[]. Size of  # arr1[] is n-1. def findExtra(arr1, arr2, n) :     for i in range(0, n) :         if (arr1[i] != arr2[i]) :             return i        return n       # Driver code arr1 = [2, 4, 6, 8,  10, 12, 13] arr2 = [2, 4, 6, 8, 10, 12] n = len(arr2)    # Solve is passed both arrays print(findExtra(arr1, arr2, n))    # This code is contributed  # by Nikita Tiwari.

## C#

 // C# program to find an extra  // element present in arr1[] using System;    class GfG  {            // Returns index of extra     // element in arr1[]. n is     // size of arr2[]. Size of     // arr1[] is n-1.     static int findExtra(int []arr1,                          int []arr2, int n)     {         for (int i = 0; i < n; i++)             if (arr1[i] != arr2[i])                 return i;                    return n;     }            // Driver code     public static void Main ()     {         int []arr1 = {2, 4, 6, 8,                       10, 12, 13};         int []arr2 = {2, 4, 6,                        8, 10, 12};         int n = arr2.Length;                // Solve is passed both arrays         Console.Write(findExtra(arr1, arr2, n));     } }    // This code is contributed by parashar.

## PHP



Output :

6

Time complexity : O(n)

Method 2 (Using Binary search)

We use binary search to check whether the same indices elements are different & reduce our search by a factor of 2 in each step.

## C++

 // C++ program to find an extra // element present in arr1[] #include using namespace std;    // Returns index of extra element // in arr1[]. n is size of arr2[].  // Size of arr1[] is n-1. int findExtra(int arr1[],                int arr2[], int n) {     // Initialize result     int index = n;         // left and right are end      // points denoting the current range.     int left = 0, right = n - 1;     while (left <= right)     {         int mid = (left + right) / 2;            // If middle element is same          // of both arrays, it means          // that extra element is after          // mid so we update left to mid+1         if (arr2[mid] == arr1[mid])             left = mid + 1;            // If middle element is different          // of the arrays, it means that          // the index we are searching for          // is either mid, or before mid.          // Hence we update right to mid-1.         else         {             index = mid;             right = mid - 1;         }     }        // when right is greater than      // left our search is complete.     return index; }    // Driver code int main() {     int arr1[] = {2, 4, 6, 8, 10, 12, 13};     int arr2[] = {2, 4, 6, 8, 10, 12};     int n = sizeof(arr2) / sizeof(arr2[0]);        // Solve is passed both arrays     cout << findExtra(arr1, arr2, n);     return 0; }

## Java

 // Java program to find an extra  // element present in arr1[] class GFG {     // Returns index of extra element      // in arr1[]. n is size of arr2[].     // Size of arr1[] is n-1.     static int findExtra(int arr1[],                           int arr2[], int n)     {         // Initialize result         int index = n;                 // left and right are end          // points denoting the current range.         int left = 0, right = n - 1;         while (left <= right)         {             int mid = (left+right) / 2;                    // If middle element is same              // of both arrays, it means              // that extra element is after              // mid so we update left to mid+1             if (arr2[mid] == arr1[mid])                 left = mid + 1;                    // If middle element is different             // of the arrays, it means that              // the index we are searching for             // is either mid, or before mid.              // Hence we update right to mid-1.             else             {                 index = mid;                 right = mid - 1;             }         }                // when right is greater than          // left, our search is complete.         return index;     }            // Driver Code     public static void main (String[] args)     {         int arr1[] = {2, 4, 6, 8, 10, 12,13};         int arr2[] = {2, 4, 6, 8, 10, 12};         int n = arr2.length;                // Solve is passed both arrays         System.out.println(findExtra(arr1, arr2, n));     } }    // This code is contributed by Harsh Agarwal

## Python3

 # Python3 program to find an extra # element present in arr1[]    # Returns index of extra element  # in arr1[]. n is size of arr2[].  # Size of arr1[] is n-1. def findExtra(arr1, arr2, n) :        index = n # Initialize result        # left and right are end points      # denoting the current range.     left = 0     right = n - 1     while (left <= right) :         mid = (int)((left + right) / 2)            # If middle element is same          # of both arrays, it means          # that extra element is after          # mid so we update left to          # mid + 1         if (arr2[mid] == arr1[mid]) :             left = mid + 1            # If middle element is different          # of the arrays, it means that          # the index we are searching for         # is either mid, or before mid.         # Hence we update right to mid-1.         else :             index = mid             right = mid - 1                # when right is greater than left our     # search is complete.     return index    # Driver code arr1 = [2, 4, 6, 8, 10, 12, 13] arr2 = [2, 4, 6, 8, 10, 12] n = len(arr2)    # Solve is passed both arrays print(findExtra(arr1, arr2, n))    # This code is contributed by Nikita Tiwari.

## C#

 // C# program to find an extra  // element present in arr1[] using System;    class GFG {            // Returns index of extra     // element in arr1[]. n is     // size of arr2[].      // Size of arr1[] is     // n - 1.     static int findExtra(int []arr1,                           int []arr2,                           int n)     {                    // Initialize result         int index = n;                 // left and right are         // end points denoting         // the current range.         int left = 0, right = n - 1;         while (left <= right)         {             int mid = (left+right) / 2;                    // If middle element is             // same of both arrays,             // it means that extra              // element is after mid             // so we update left             // to mid + 1             if (arr2[mid] == arr1[mid])                 left = mid + 1;                    // If middle element is              // different of the arrays,             // it means that the index             // we are searching for is             // either mid, or before mid.             // Hence we update right to mid-1.             else             {                 index = mid;                 right = mid - 1;             }         }                // when right is greater         // than left our         // search is complete.         return index;     }            // Driver Code     public static void Main ()     {         int []arr1 = {2, 4, 6, 8, 10, 12,13};         int []arr2 = {2, 4, 6, 8, 10, 12};         int n = arr2.Length;                // Solve is passed          // both arrays         Console.Write(findExtra(arr1, arr2, n));     } }    // This code is contributed by nitin mittal.

## PHP



Output :

6

Time complexity : O(log n)

Method 3(Using predefined function):
We use a pre-defined function to calculate the index of the extra element. The extra element can be easily found by adding all the elements of array 2 and then subtracting the sum from that of the elements of array 1.

Below is the implementation of the above approach:

## Java

 // Java code for above approach class GFG  {        // Function to find Index      static int find_extra_element_index(int[] arrA,                                          int[] arrB)      {            // Calculating extra element         int extra_element = sum(arrA) - sum(arrB);                    // returns index of extra element         return indexOf(arrA, extra_element);     }            // function return sum of array elements     static int sum(int[] arr)     {         int sum = 0;         for (int i = 0; i < arr.length; i++)         {             sum += arr[i];         }         return sum;     }            // function return index of given element     static int indexOf(int[] arr, int element)      {         for (int i = 0; i < arr.length; i++)         {             if (arr[i] == element)             {                 return i;             }         }         return -1;     }            // Driver Code     public static void main(String[] args)      {         int[] arrA = {2, 4, 6, 8, 10, 12, 13};         int[] arrB = {2, 4, 6, 8, 10, 12};         System.out.println(find_extra_element_index(arrA, arrB));     } }    /* This code contributed by PrinciRaj1992 */

## Python3

 # Python3 code for above approach    # Function to find Index  def find_extra_element_index(arrA, arrB):            # Calculating extra element     extra_element = sum(arrA) - sum(arrB)            # returns index of extra element     return arrA.index(extra_element)    # Driver Code arrA = [2, 4, 6, 8, 10, 12, 13] arrB = [2, 4, 6, 8, 10, 12] print(find_extra_element_index(arrA,arrB))    # This code is contributed by Dravid

## C#

 // C# code for above approach using System;    class GFG  {        // Function to find Index      static int find_extra_element_index(int[] arrA,                                          int[] arrB)      {            // Calculating extra element         int extra_element = sum(arrA) - sum(arrB);                    // returns index of extra element         return indexOf(arrA, extra_element);     }            // function return sum of array elements     static int sum(int[] arr)     {         int sum = 0;         for (int i = 0; i < arr.Length; i++)         {             sum += arr[i];         }         return sum;     }            // function return index of given element     static int indexOf(int[] arr, int element)      {         for (int i = 0; i < arr.Length; i++)         {             if (arr[i] == element)             {                 return i;             }         }         return -1;     }            // Driver Code     public static void Main(String[] args)      {         int[] arrA = {2, 4, 6, 8, 10, 12, 13};         int[] arrB = {2, 4, 6, 8, 10, 12};         Console.WriteLine(find_extra_element_index(arrA, arrB));     } }    // This code has been contributed by 29AjayKumar

Output :

6

Time complexity : O(1)