Tutorialspoint.dev

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 <iostream>
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

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, 810, 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

<?php
// PHP 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.
function findExtra($arr1
                   $arr2, $n)
{
for ($i = 0; $i < $n; $i++)
    if ($arr1[$i] != $arr2[$i])
        return $i;
  
return $n;
}
  
// Driver code
$arr1 = array (2, 4, 6, 8, 
               10, 12, 13);
$arr2 = array(2, 4, 6, 
              8, 10, 12);
$n = sizeof($arr2);
  
// Solve is passed
// both arrays
echo findExtra($arr1, $arr2, $n);
  
// This code is contributed by ajit
?>


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 <iostream>
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

<?php
// PHP 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.
function findExtra($arr1, $arr2, $n)
{
    // Initialize result
    $index = $n
  
    // left and right are 
    // end points denoting
    // the current range.
    $left = 0; $right = $n - 1;
    while ($left <= $right)
    {
        $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
{
    $arr1 = array(2, 4, 6, 8, 
                  10, 12, 13);
    $arr2 = array(2, 4, 6, 
                  8, 10, 12);
    $n = sizeof($arr2) / sizeof($arr2[0]);
  
    // Solve is passed both arrays
    echo findExtra($arr1, $arr2, $n);
    return 0;
  
// This code is contributed by nitin mittal
?>


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)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter