Encuentre el índice de un elemento adicional presente en una array ordenada

Dadas dos arrays ordenadas. Solo hay 1 diferencia entre las arrays. La primera array tiene un elemento adicional agregado en el medio. Encuentre el índice del elemento adicional.

Ejemplos: 

Input: {2, 4, 6, 8, 9, 10, 12};
       {2, 4, 6, 8, 10, 12};
Output: 4
Explanation: 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
Explanation: The first array has an extra element 9.
The extra element is present at index 3.

Método 1: Esto incluye el enfoque básico para resolver este problema en particular. 

Enfoque: el método básico es iterar a través de toda la segunda array y verificar elemento por elemento si son diferentes. A medida que se ordena la array, la verificación de la posición adyacente de dos arrays debe ser similar hasta que se encuentre el elemento que falta. 

Algoritmo: 

  1. Atraviesa la array de principio a fin.
  2. Compruebe si el elemento en el i-ésimo elemento de las dos arrays es similar o no.
  3. Si los elementos no son similares, imprima el índice y rompa

Implementación: 

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

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

Javascript

<script>
// JavaScript 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 (let i = 0; i < n; i++)
    if (arr1[i] != arr2[i])
        return i;
 
return n;
}
 
// Driver code
 
    let arr1 = [2, 4, 6, 8,
                10, 12, 13];
    let arr2 = [2, 4, 6,
                8, 10, 12];
    let n = arr2.length;
 
    // Solve is passed both arrays
    document.write(findExtra(arr1, arr2, n));
 
// This code is contributed by Surbhi Tyagi.
</script>
Producción

6

Análisis de Complejidad: 

  • Complejidad temporal: O(n). 
    Como se necesita un recorrido a través de la array, la complejidad del tiempo es lineal.
  • Complejidad espacial: O(1). 
    Dado que no se requiere espacio adicional, la complejidad del tiempo es constante.

Método 2: Este método es una mejor manera de resolver el problema anterior y utiliza el concepto de búsqueda binaria. 

Enfoque: Para encontrar el índice del elemento faltante en menos de un tiempo lineal, se puede usar la búsqueda binaria, la idea es que todos los índices mayores o iguales al índice del elemento faltante tendrán diferentes elementos tanto en las arrays como en todos los los índices menores que ese índice tendrán elementos similares en ambas arrays.

Algoritmo: 

  1. Cree tres variables, bajo = 0 , alto = n-1 , medio , ans = n
  2. Ejecute un ciclo hasta que el mínimo sea menor o igual que el máximo, es decir, hasta que nuestro rango de búsqueda sea menor que cero.
  3. Si el elemento medio, es decir, (bajo + alto)/2, de ambas arrays es similar, actualice la búsqueda a la segunda mitad del rango de búsqueda, es decir, bajo = medio + 1
  4. De lo contrario, actualice la búsqueda a la primera mitad del rango de búsqueda, es decir, alto = medio – 1 , y actualice la respuesta al índice actual, ans = medio
  5. Imprime el índice.

Implementación: 

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

Javascript

<script>
 
 
// Javascript 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
    let index = n;
 
    // left and right are end
    // points denoting the current range.
    let left = 0, right = n - 1;
    while (left <= right)
    {
        let mid = Math.floor((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 program
     
    let arr1 = [2, 4, 6, 8, 10, 12, 13];
    let arr2 = [2, 4, 6, 8, 10, 12];
    let n = arr2.length;
 
    // Solve is passed both arrays
    document.write(findExtra(arr1, arr2, n));
     
     
</script>
Producción

6

Análisis de Complejidad: 

  • Complejidad temporal: O(log n). 
    La complejidad temporal de la búsqueda binaria es O(log n)
  • Complejidad espacial : O(1). 
    Como no se requiere espacio adicional, la complejidad del tiempo es constante.

Método 3: Este método resuelve el problema dado usando la función predefinida. 

Enfoque: para encontrar el elemento que es diferente, encuentre la suma de cada array y reste las sumas y encuentre el valor absoluto. Busque la array más grande y verifique si el absoluto es igual a un índice y devuelva ese índice. Si falta un elemento y todos los demás elementos son iguales, entonces la diferencia de sumas será igual al elemento faltante.

Algoritmo:

  1. Crea una función para calcular la suma de dos arrays.
  2. Encuentre la diferencia absoluta entre la suma de dos arrays ( valor ).
  3. Atraviesa la array más grande desde el principio hasta el final
  4. Si el elemento en cualquier índice es igual al valor, imprima el índice y rompa el ciclo.

Implementación: 

C++

// C++ code for above approach
#include<bits/stdc++.h>
using namespace std;
 
// function return sum of array elements
int sum(int arr[], int n)
{
    int summ = 0;
    for (int i = 0; i < n; i++)
    {
        summ += arr[i];
    }
    return summ;
}
 
// function return index of given element
int indexOf(int arr[], int element, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == element)
        {
            return i;
        }
    }
    return -1;
}
 
// Function to find Index
int find_extra_element_index(int arrA[],
                             int arrB[],
                             int n, int m)
{
 
    // Calculating extra element
    int extra_element = sum(arrA, n) -
                        sum(arrB, m);
     
    // returns index of extra element
    return indexOf(arrA, extra_element, n);
}
 
// Driver Code
int main()
{
    int arrA[] = {2, 4, 6, 8, 10, 12, 13};
    int arrB[] = {2, 4, 6, 8, 10, 12};
    int n = sizeof(arrA) / sizeof(arrA[0]);
    int m = sizeof(arrB) / sizeof(arrB[0]);
    cout << find_extra_element_index(arrA, arrB, n, m);
}
 
// This code is contributed by mohit kumar

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

Javascript

<script>
    // Javascript code for above approach
     
    // Function to find Index
    function find_extra_element_index(arrA, arrB)
    {
  
        // Calculating extra element
        let extra_element = sum(arrA) - sum(arrB);
          
        // returns index of extra element
        return indexOf(arrA, extra_element);
    }
      
    // function return sum of array elements
    function sum(arr)
    {
        let sum = 0;
        for (let i = 0; i < arr.length; i++)
        {
            sum += arr[i];
        }
        return sum;
    }
      
    // function return index of given element
    function indexOf(arr, element)
    {
        for (let i = 0; i < arr.length; i++)
        {
            if (arr[i] == element)
            {
                return i;
            }
        }
        return -1;
    }
     
    let arrA = [2, 4, 6, 8, 10, 12, 13];
    let arrB = [2, 4, 6, 8, 10, 12];
    document.write(find_extra_element_index(arrA, arrB));
     
</script>
Producción

6

Análisis de Complejidad: 

  • Complejidad temporal: O(n). 
    Dado que solo se necesitan tres recorridos a través de la array, la complejidad del tiempo es lineal.
  • Complejidad espacial: O(1). 
    Como no se requiere espacio adicional, la complejidad del tiempo es constante.

Este artículo es una contribución de Abhishek Khatri . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *