# 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); ` ` `  `    ``// 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 `

## 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); ` ` `  `    ``// 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)