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:
- Atraviesa la array de principio a fin.
- Compruebe si el elemento en el i-ésimo elemento de las dos arrays es similar o no.
- 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:
- Cree tres variables, bajo = 0 , alto = n-1 , medio , ans = n
- 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.
- 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
- 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
- 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:
- Crea una función para calcular la suma de dos arrays.
- Encuentre la diferencia absoluta entre la suma de dos arrays ( valor ).
- Atraviesa la array más grande desde el principio hasta el final
- 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