Dada una array no ordenada arr[] de N enteros que están en progresión aritmética , la tarea es imprimir el elemento faltante de la serie dada.
Ejemplos:
Entrada: arr[] = {12, 3, 6, 15, 18}
Salida: 9
Explicación:
Los elementos dados en orden son: 3, 6, 12, 15, 18.
Por lo tanto, el elemento faltante es 9.Entrada: arr[] = {2, 8, 6, 10}
Salida: 4
Explicación:
Los elementos dados en orden son: 2, 6, 8, 10.
Por lo tanto, el elemento faltante es 4.
Enfoque ingenuo: la idea es utilizar la búsqueda binaria . Ordene la array dada, luego la array se organizará en orden de serie AP, podemos aplicar la búsqueda binaria (como en este artículo ) como se describe a continuación:
- Encuentre el elemento del medio y verifique si la diferencia entre el elemento del medio y el elemento siguiente al elemento del medio es igual a la diferencia común o no, de lo contrario, el elemento que falta se encuentra entre mid y mid + 1 .
- Si el elemento del medio es igual a (N/2) el término en la serie aritmética dada, entonces el elemento que falta se encuentra en el lado derecho del elemento del medio.
- De lo contrario, el elemento se encuentra en el lado izquierdo del elemento central.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the missing element
int findMissing(int arr[], int left,
int right, int diff)
{
// Fix left and right boundary
// for binary search
if (right <= left)
return INT_MAX;
// Find index of middle element
int mid = left + (right - left) / 2;
// Check if the element just after
// the middle element is missing
if (arr[mid + 1] - arr[mid] != diff)
return (arr[mid] + diff);
// Check if the element just
// before mid is missing
if (mid > 0
&& arr[mid] - arr[mid - 1] != diff)
return (arr[mid - 1] + diff);
// Check if the elements till mid
// follow the AP, then recur
// for right half
if (arr[mid] == arr[0] + mid * diff)
return findMissing(arr, mid + 1,
right, diff);
// Else recur for left half
return findMissing(arr, left,
mid - 1, diff);
}
// Function to find the missing
// element in AP series
int missingElement(int arr[], int n)
{
// Sort the array arr[]
sort(arr, arr + n);
// Calculate Common Difference
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
return findMissing(arr, 0, n - 1, diff);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 8, 6, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << missingElement(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function to find the missing element
static int findMissing(int arr[], int left,
int right, int diff)
{
// Fix left and right boundary
// for binary search
if (right <= left)
return 0;
// Find index of middle element
int mid = left + (right - left) / 2;
// Check if the element just after
// the middle element is missing
if (arr[mid + 1] - arr[mid] != diff)
return (arr[mid] + diff);
// Check if the element just
// before mid is missing
if (mid > 0 &&
arr[mid] - arr[mid - 1] != diff)
return (arr[mid - 1] + diff);
// Check if the elements till mid
// follow the AP, then recur
// for right half
if (arr[mid] == arr[0] + mid * diff)
return findMissing(arr, mid + 1,
right, diff);
// Else recur for left half
return findMissing(arr, left,
mid - 1, diff);
}
// Function to find the missing
// element in AP series
static int missingElement(int arr[], int n)
{
// Sort the array arr[]
Arrays.sort(arr);
// Calculate Common Difference
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
return findMissing(arr, 0, n - 1, diff);
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = new int[]{ 2, 8, 6, 10 };
int n = arr.length;
// Function Call
System.out.println(missingElement(arr, n));
}
}
// This code is contributed by rock_cool
Python3
# Python3 program for the above approach import sys # Function to find the missing element def findMissing(arr, left, right, diff): # Fix left and right boundary # for binary search if (right <= left): return sys.maxsize # Find index of middle element mid = left + (right - left) // 2 # Check if the element just after # the middle element is missing if (arr[mid + 1] - arr[mid] != diff): return (arr[mid] + diff) # Check if the element just # before mid is missing if (mid > 0 and arr[mid] - arr[mid - 1] != diff): return (arr[mid - 1] + diff) # Check if the elements till mid # follow the AP, then recur # for right half if (arr[mid] == arr[0] + mid * diff): return findMissing(arr, mid + 1, right, diff) # Else recur for left half return findMissing(arr, left, mid - 1, diff) # Function to find the missing # element in AP series def missingElement(arr, n): # Sort the array arr[] arr.sort() # Calculate Common Difference diff = (arr[n - 1] - arr[0]) // n # Binary search for the missing return findMissing(arr, 0, n - 1, diff) # Driver Code # Given array arr[] arr = [ 2, 8, 6, 10 ] n = len(arr) # Function call print(missingElement(arr, n)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the missing element
static int findMissing(int []arr, int left,
int right, int diff)
{
// Fix left and right boundary
// for binary search
if (right <= left)
return 0;
// Find index of middle element
int mid = left + (right - left) / 2;
// Check if the element just after
// the middle element is missing
if (arr[mid + 1] - arr[mid] != diff)
return (arr[mid] + diff);
// Check if the element just
// before mid is missing
if (mid > 0 &&
arr[mid] - arr[mid - 1] != diff)
return (arr[mid - 1] + diff);
// Check if the elements till mid
// follow the AP, then recur
// for right half
if (arr[mid] == arr[0] + mid * diff)
return findMissing(arr, mid + 1,
right, diff);
// Else recur for left half
return findMissing(arr, left,
mid - 1, diff);
}
// Function to find the missing
// element in AP series
static int missingElement(int []arr, int n)
{
// Sort the array []arr
Array.Sort(arr);
// Calculate Common Difference
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
return findMissing(arr, 0, n - 1, diff);
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = new int[]{ 2, 8, 6, 10 };
int n = arr.Length;
// Function Call
Console.WriteLine(missingElement(arr, n));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program for the above approach
// Function to find the missing element
function findMissing(arr, left, right, diff)
{
// Fix left and right boundary
// for binary search
if (right <= left)
return 0;
// Find index of middle element
let mid = left + parseInt((right - left) / 2, 10);
// Check if the element just after
// the middle element is missing
if (arr[mid + 1] - arr[mid] != diff)
return (arr[mid] + diff);
// Check if the element just
// before mid is missing
if (mid > 0 &&
arr[mid] - arr[mid - 1] != diff)
return (arr[mid - 1] + diff);
// Check if the elements till mid
// follow the AP, then recur
// for right half
if (arr[mid] == arr[0] + mid * diff)
return findMissing(arr, mid + 1,
right, diff);
// Else recur for left half
return findMissing(arr, left,
mid - 1, diff);
}
// Function to find the missing
// element in AP series
function missingElement(arr, n)
{
// Sort the array []arr
arr.sort(function(a, b){return a - b});
// Calculate Common Difference
let diff = parseInt((arr[n - 1] -
arr[0]) / n, 10);
// Binary search for the missing
return findMissing(arr, 0, n - 1, diff);
}
// Driver code
// Given array []arr
let arr = [ 2, 8, 6, 10 ];
let n = arr.length;
// Function Call
document.write(missingElement(arr, n));
// This code is contributed by rameshtravel07
</script>
Producción:
4
Complejidad de tiempo: O(N*log 2 N)
Enfoque eficiente: Para optimizar el método anterior, usaremos las siguientes propiedades de XOR que es a ^ a = 0 , por lo tanto, (a ^ b ^ c) ^ (a ^ c) = segundo A continuación se muestran los pasos:
- Encuentre los elementos máximo y mínimo de la array dada.
- Encuentre la diferencia común como:
- Calcule xor para todos los elementos de la array.
- Realice xor con todos los elementos de la serie real para encontrar el valor resultante que es el elemento que falta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the missing element
int missingElement(int arr[], int n)
{
// For maximum Element in the array
int max_ele = arr[0];
// For minimum Element in the array
int min_ele = arr[0];
// For xor of all elements
int x = 0;
// Common difference of AP series
int d;
// find maximum and minimum element
for (int i = 0; i < n; i++) {
if (arr[i] > max_ele)
max_ele = arr[i];
if (arr[i] < min_ele)
min_ele = arr[i];
}
// Calculating common difference
d = (max_ele - min_ele) / n;
// Calculate the XOR of all elements
for (int i = 0; i < n; i++) {
x = x ^ arr[i];
}
// Perform XOR with actual AP series
// resultant x will be the ans
for (int i = 0; i <= n; i++) {
x = x ^ (min_ele + (i * d));
}
// Return the missing element
return x;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 12, 3, 6, 15, 18 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
int element = missingElement(arr, n);
// Print the missing element
cout << element;
}
Java
// Java program for the above approach
class GFG{
// Function to get the missing element
static int missingElement(int arr[], int n)
{
// For maximum Element in the array
int max_ele = arr[0];
// For minimum Element in the array
int min_ele = arr[0];
// For xor of all elements
int x = 0;
// Common difference of AP series
int d;
// find maximum and minimum element
for(int i = 0; i < n; i++)
{
if (arr[i] > max_ele)
max_ele = arr[i];
if (arr[i] < min_ele)
min_ele = arr[i];
}
// Calculating common difference
d = (max_ele - min_ele) / n;
// Calculate the XOR of all elements
for(int i = 0; i < n; i++)
{
x = x ^ arr[i];
}
// Perform XOR with actual AP series
// resultant x will be the ans
for(int i = 0; i <= n; i++)
{
x = x ^ (min_ele + (i * d));
}
// Return the missing element
return x;
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = new int[]{ 12, 3, 6, 15, 18 };
int n = arr.length;
// Function Call
int element = missingElement(arr, n);
// Print the missing element
System.out.print(element);
}
}
// This code is contributed by Pratima Pandey
Python3
# Python3 program for the above approach # Function to get the missing element def missingElement(arr, n): # For maximum element in the array max_ele = arr[0] # For minimum Element in the array min_ele = arr[0] # For xor of all elements x = 0 # Common difference of AP series d = 0 # Find maximum and minimum element for i in range(n): if (arr[i] > max_ele): max_ele = arr[i] if (arr[i] < min_ele): min_ele = arr[i] # Calculating common difference d = (max_ele - min_ele) // n # Calculate the XOR of all elements for i in range(n): x = x ^ arr[i] # Perform XOR with actual AP series # resultant x will be the ans for i in range(n + 1): x = x ^ (min_ele + (i * d)) # Return the missing element return x # Driver Code if __name__ == '__main__': # Given array arr = [ 12, 3, 6, 15, 18 ] n = len(arr) # Function Call element = missingElement(arr, n) # Print the missing element print(element) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to get the missing element
static int missingElement(int[] arr, int n)
{
// For maximum Element in the array
int max_ele = arr[0];
// For minimum Element in the array
int min_ele = arr[0];
// For xor of all elements
int x = 0;
// Common difference of AP series
int d;
// find maximum and minimum element
for(int i = 0; i < n; i++)
{
if (arr[i] > max_ele)
max_ele = arr[i];
if (arr[i] < min_ele)
min_ele = arr[i];
}
// Calculating common difference
d = (max_ele - min_ele) / n;
// Calculate the XOR of all elements
for(int i = 0; i < n; i++)
{
x = x ^ arr[i];
}
// Perform XOR with actual AP series
// resultant x will be the ans
for(int i = 0; i <= n; i++)
{
x = x ^ (min_ele + (i * d));
}
// Return the missing element
return x;
}
// Driver code
public static void Main()
{
// Given array
int[] arr = new int[]{ 12, 3, 6, 15, 18 };
int n = arr.Length;
// Function Call
int element = missingElement(arr, n);
// Print the missing element
Console.Write(element);
}
}
// This code is contributed by Ritik Bansal
Javascript
<script>
// Javascript program for the above approach
// Function to get the missing element
function missingElement(arr, n)
{
// For maximum Element in the array
let max_ele = arr[0];
// For minimum Element in the array
let min_ele = arr[0];
// For xor of all elements
let x = 0;
// Common difference of AP series
let d;
// find maximum and minimum element
for (let i = 0; i < n; i++) {
if (arr[i] > max_ele)
max_ele = arr[i];
if (arr[i] < min_ele)
min_ele = arr[i];
}
// Calculating common difference
d = parseInt((max_ele - min_ele) / n, 10);
// Calculate the XOR of all elements
for (let i = 0; i < n; i++) {
x = x ^ arr[i];
}
// Perform XOR with actual AP series
// resultant x will be the ans
for (let i = 0; i <= n; i++) {
x = x ^ (min_ele + (i * d));
}
// Return the missing element
return x;
}
// Given array
let arr = [ 12, 3, 6, 15, 18 ];
let n = arr.length;
// Function Call
let element = missingElement(arr, n);
// Print the missing element
document.write(element);
</script>
Producción:
9
Complejidad temporal: O(N)
Espacio auxiliar: O(1)