Dadas dos arrays que son duplicados entre sí, excepto un elemento, es decir, falta un elemento de una de las arrays, necesitamos encontrar ese elemento faltante.
Ejemplos:
C++
// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Function to find missing element based on binary
// search approach. arr1[] is of larger size and
// N is size of it. arr1[] and arr2[] are assumed
// to be in same order.
int findMissingUtil(int arr1[], int arr2[], int N)
{
// special case, for only element which is
// missing in second array
if (N == 1)
return arr1[0];
// special case, for first element missing
if (arr1[0] != arr2[0])
return arr1[0];
// Initialize current corner points
int lo = 0, hi = N - 1;
// loop until lo < hi
while (lo < hi)
{
int mid = (lo + hi) / 2;
// If element at mid indices are equal
// then go to right subarray
if (arr1[mid] == arr2[mid])
lo = mid;
else
hi = mid;
// if lo, hi becomes contiguous, break
if (lo == hi - 1)
break;
}
// missing element will be at hi index of
// bigger array
return arr1[hi];
}
// This function mainly does basic error checking
// and calls findMissingUtil
void findMissing(int arr1[], int arr2[], int M, int N)
{
if (N == M-1)
cout << "Missing Element is "
<< findMissingUtil(arr1, arr2, M) << endl;
else if (M == N-1)
cout << "Missing Element is "
<< findMissingUtil(arr2, arr1, N) << endl;
else
cout << "Invalid Input";
}
// Driver Code
int main()
{
int arr1[] = {1, 4, 5, 7, 9};
int arr2[] = {4, 5, 7, 9};
int M = sizeof(arr1) / sizeof(int);
int N = sizeof(arr2) / sizeof(int);
findMissing(arr1, arr2, M, N);
return 0;
}
Java
// Java program to find missing element
// from same arrays
// (except one missing element)
import java.io.*;
class MissingNumber {
/* Function to find missing element based
on binary search approach. arr1[] is of
larger size and N is size of it.arr1[] and
arr2[] are assumed to be in same order. */
int findMissingUtil(int arr1[], int arr2[],
int N)
{
// special case, for only element
// which is missing in second array
if (N == 1)
return arr1[0];
// special case, for first
// element missing
if (arr1[0] != arr2[0])
return arr1[0];
// Initialize current corner points
int lo = 0, hi = N - 1;
// loop until lo < hi
while (lo < hi) {
int mid = (lo + hi) / 2;
// If element at mid indices are
// equal then go to right subarray
if (arr1[mid] == arr2[mid])
lo = mid;
else
hi = mid;
// if lo, hi becomes
// contiguous, break
if (lo == hi - 1)
break;
}
// missing element will be at hi
// index of bigger array
return arr1[hi];
}
// This function mainly does basic error
// checking and calls findMissingUtil
void findMissing(int arr1[], int arr2[],
int M, int N)
{
if (N == M - 1)
System.out.println("Missing Element is "
+ findMissingUtil(arr1, arr2, M) + "\n");
else if (M == N - 1)
System.out.println("Missing Element is "
+ findMissingUtil(arr2, arr1, N) + "\n");
else
System.out.println("Invalid Input");
}
// Driver Code
public static void main(String args[])
{
MissingNumber obj = new MissingNumber();
int arr1[] = { 1, 4, 5, 7, 9 };
int arr2[] = { 4, 5, 7, 9 };
int M = arr1.length;
int N = arr2.length;
obj.findMissing(arr1, arr2, M, N);
}
}
// This code is contributed by Anshika Goyal.
Python3
# Python3 program to find missing
# element from same arrays
# (except one missing element)
# Function to find missing element based
# on binary search approach. arr1[] is
# of larger size and N is size of it.
# arr1[] and arr2[] are assumed
# to be in same order.
def findMissingUtil(arr1, arr2, N):
# special case, for only element
# which is missing in second array
if N == 1:
return arr1[0];
# special case, for first
# element missing
if arr1[0] != arr2[0]:
return arr1[0]
# Initialize current corner points
lo = 0
hi = N - 1
# loop until lo < hi
while (lo < hi):
mid = (lo + hi) / 2
# If element at mid indices
# are equal then go to
# right subarray
if arr1[mid] == arr2[mid]:
lo = mid
else:
hi = mid
# if lo, hi becomes
# contiguous, break
if lo == hi - 1:
break
# missing element will be at
# hi index of bigger array
return arr1[hi]
# This function mainly does basic
# error checking and calls
# findMissingUtil
def findMissing(arr1, arr2, M, N):
if N == M-1:
print("Missing Element is",
findMissingUtil(arr1, arr2, M))
elif M == N-1:
print("Missing Element is",
findMissingUtil(arr2, arr1, N))
else:
print("Invalid Input")
# Driver Code
arr1 = [1, 4, 5, 7, 9]
arr2 = [4, 5, 7, 9]
M = len(arr1)
N = len(arr2)
findMissing(arr1, arr2, M, N)
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find missing element from
// same arrays (except one missing element)
using System;
class GFG {
/* Function to find missing element based
on binary search approach. arr1[] is of
larger size and N is size of it.arr1[] and
arr2[] are assumed to be in same order. */
static int findMissingUtil(int []arr1,
int []arr2, int N)
{
// special case, for only element
// which is missing in second array
if (N == 1)
return arr1[0];
// special case, for first
// element missing
if (arr1[0] != arr2[0])
return arr1[0];
// Initialize current corner points
int lo = 0, hi = N - 1;
// loop until lo < hi
while (lo < hi) {
int mid = (lo + hi) / 2;
// If element at mid indices are
// equal then go to right subarray
if (arr1[mid] == arr2[mid])
lo = mid;
else
hi = mid;
// if lo, hi becomes
// contiguous, break
if (lo == hi - 1)
break;
}
// missing element will be at hi
// index of bigger array
return arr1[hi];
}
// This function mainly does basic error
// checking and calls findMissingUtil
static void findMissing(int []arr1, int []arr2,
int M, int N)
{
if (N == M - 1)
Console.WriteLine("Missing Element is "
+ findMissingUtil(arr1, arr2, M) + "\n");
else if (M == N - 1)
Console.WriteLine("Missing Element is "
+ findMissingUtil(arr2, arr1, N) + "\n");
else
Console.WriteLine("Invalid Input");
}
// Driver Code
public static void Main()
{
int []arr1 = { 1, 4, 5, 7, 9 };
int []arr2 = { 4, 5, 7, 9 };
int M = arr1.Length;
int N = arr2.Length;
findMissing(arr1, arr2, M, N);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find missing
// element from same arrays
// (except one missing element)
// Function to find missing
// element based on binary
// search approach. arr1[]
// is of larger size and
// N is size of it. arr1[]
// and arr2[] are assumed
// to be in same order.
function findMissingUtil($arr1, $arr2, $N)
{
// special case, for only
// element which is
// missing in second array
if ($N == 1)
return $arr1[0];
// special case, for first
// element missing
if ($arr1[0] != $arr2[0])
return $arr1[0];
// Initialize current
// corner points
$lo = 0;
$hi = $N - 1;
// loop until lo < hi
while ($lo < $hi)
{
$mid = ($lo + $hi) / 2;
// If element at mid indices are
// equal then go to right subarray
if ($arr1[$mid] == $arr2[$mid])
$lo = $mid;
else
$hi = $mid;
// if lo, hi becomes
// contiguous, break
if ($lo == $hi - 1)
break;
}
// missing element will be
// at hi index of
// bigger array
return $arr1[$hi];
}
// This function mainly
// does basic error checking
// and calls findMissingUtil
function findMissing($arr1, $arr2,
$M, $N)
{
if ($N == $M - 1)
echo "Missing Element is "
, findMissingUtil($arr1,
$arr2, $M) ;
else if ($M == $N - 1)
echo "Missing Element is "
, findMissingUtil($arr2,
$arr1, $N);
else
echo "Invalid Input";
}
// Driver Code
$arr1 = array(1, 4, 5, 7, 9);
$arr2 = array(4, 5, 7, 9);
$M = count($arr1);
$N = count($arr2);
findMissing($arr1, $arr2, $M, $N);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find missing element from
// same arrays (except one missing element)
/* Function to find missing element based
on binary search approach. arr1[] is of
larger size and N is size of it.arr1[] and
arr2[] are assumed to be in same order. */
function findMissingUtil(arr1, arr2, N)
{
// special case, for only element
// which is missing in second array
if (N == 1)
return arr1[0];
// special case, for first
// element missing
if (arr1[0] != arr2[0])
return arr1[0];
// Initialize current corner points
let lo = 0, hi = N - 1;
// loop until lo < hi
while (lo < hi) {
let mid = parseInt((lo + hi) / 2, 10);
// If element at mid indices are
// equal then go to right subarray
if (arr1[mid] == arr2[mid])
lo = mid;
else
hi = mid;
// if lo, hi becomes
// contiguous, break
if (lo == hi - 1)
break;
}
// missing element will be at hi
// index of bigger array
return arr1[hi];
}
// This function mainly does basic error
// checking and calls findMissingUtil
function findMissing(arr1, arr2, M, N)
{
if (N == M - 1)
document.write("Missing Element is "
+ findMissingUtil(arr1, arr2, M) + "</br>");
else if (M == N - 1)
document.write("Missing Element is "
+ findMissingUtil(arr2, arr1, N) + "</br>");
else
document.write("Invalid Input" + "</br>");
}
let arr1 = [ 1, 4, 5, 7, 9 ];
let arr2 = [ 4, 5, 7, 9 ];
let M = arr1.length;
let N = arr2.length;
findMissing(arr1, arr2, M, N);
</script>
CPP
// C++ program to find missing element from one array
// such that it has all elements of other array except
// one. Elements in two arrays can be in any order.
#include <bits/stdc++.h>
using namespace std;
// This function mainly does XOR of all elements
// of arr1[] and arr2[]
void findMissing(int arr1[], int arr2[], int M,
int N)
{
if (M != N-1 && N != M-1)
{
cout << "Invalid Input";
return;
}
// Do XOR of all element
int res = 0;
for (int i=0; i<M; i++)
res = res^arr1[i];
for (int i=0; i<N; i++)
res = res^arr2[i];
cout << "Missing element is " << res;
}
// Driver Code
int main()
{
int arr1[] = {4, 1, 5, 9, 7};
int arr2[] = {7, 5, 9, 4};
int M = sizeof(arr1) / sizeof(int);
int N = sizeof(arr2) / sizeof(int);
findMissing(arr1, arr2, M, N);
return 0;
}
Java
// Java program to find missing element
// from one array such that it has all
// elements of other array except one.
// Elements in two arrays can be in any order.
import java.io.*;
class Missing {
// This function mainly does XOR of
// all elements of arr1[] and arr2[]
void findMissing(int arr1[], int arr2[],
int M, int N)
{
if (M != N - 1 && N != M - 1) {
System.out.println("Invalid Input");
return;
}
// Do XOR of all element
int res = 0;
for (int i = 0; i < M; i++)
res = res ^ arr1[i];
for (int i = 0; i < N; i++)
res = res ^ arr2[i];
System.out.println("Missing element is "
+ res);
}
// Driver Code
public static void main(String args[])
{
Missing obj = new Missing();
int arr1[] = { 4, 1, 5, 9, 7 };
int arr2[] = { 7, 5, 9, 4 };
int M = arr1.length;
int N = arr2.length;
obj.findMissing(arr1, arr2, M, N);
}
}
// This code is contributed by Anshika Goyal.
Python3
# Python 3 program to find
# missing element from one array
# such that it has all elements
# of other array except
# one. Elements in two arrays
# can be in any order.
# This function mainly does XOR of all elements
# of arr1[] and arr2[]
def findMissing(arr1,arr2, M, N):
if (M != N-1 and N != M-1):
print("Invalid Input")
return
# Do XOR of all element
res = 0
for i in range(0,M):
res = res^arr1[i];
for i in range(0,N):
res = res^arr2[i]
print("Missing element is",res)
# Driver Code
arr1 = [4, 1, 5, 9, 7]
arr2 = [7, 5, 9, 4]
M = len(arr1)
N = len(arr2)
findMissing(arr1, arr2, M, N)
# This code is contributed
# by Smitha Dinesh Semwal
C#
// C# program to find missing element
// from one array such that it has all
// elements of other array except one.
// Elements in two arrays can be in
// any order.
using System;
class GFG {
// This function mainly does XOR of
// all elements of arr1[] and arr2[]
static void findMissing(int []arr1,
int []arr2,
int M, int N)
{
if (M != N - 1 && N != M - 1)
{
Console.WriteLine("Invalid Input");
return;
}
// Do XOR of all element
int res = 0;
for (int i = 0; i < M; i++)
res = res ^ arr1[i];
for (int i = 0; i < N; i++)
res = res ^ arr2[i];
Console.WriteLine("Missing element is "
+ res);
}
// Driver Code
public static void Main()
{
int []arr1 = {4, 1, 5, 9, 7};
int []arr2 = {7, 5, 9, 4};
int M = arr1.Length;
int N = arr2.Length;
findMissing(arr1, arr2, M, N);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find missing
// element from one array
// such that it has all elements
// of other array except
// one. Elements in two arrays
// can be in any order.
// This function mainly does
// XOR of all elements
// of arr1[] and arr2[]
function findMissing($arr1, $arr2,
$M, $N)
{
if ($M != $N - 1 && $N != $M - 1)
{
echo "Invalid Input";
return;
}
// Do XOR of all element
$res = 0;
for ($i = 0; $i < $M; $i++)
$res = $res ^ $arr1[$i];
for ($i = 0; $i < $N; $i++)
$res = $res ^ $arr2[$i];
echo "Missing element is ", $res;
}
// Driver Code
$arr1 = array(4, 1, 5, 9, 7);
$arr2 = array(7, 5, 9, 4);
$M = sizeof($arr1);
$N = sizeof($arr2);
findMissing($arr1, $arr2, $M, $N);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find
// missing element from one array
// such that it has all elements
// of other array except one.
// Elements in two arrays
// can be in any order.
// This function mainly does XOR
// of all elements
// of arr1[] and arr2[]
function findMissing(arr1, arr2, M, N)
{
if (M != N-1 && N != M-1)
{
document.write("Invalid Input");
return;
}
// Do XOR of all element
let res = 0;
for (let i=0; i<M; i++)
res = res^arr1[i];
for (let i=0; i<N; i++)
res = res^arr2[i];
document.write("Missing element is " + res);
}
let arr1 = [4, 1, 5, 9, 7];
let arr2 = [7, 5, 9, 4];
let M = arr1.length;
let N = arr2.length;
findMissing(arr1, arr2, M, N);
</script>
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