Programa en C para encontrar un par con la diferencia dada

Dada una array no ordenada y un número n, encuentre si existe un par de elementos en la array cuya diferencia es n. 
Ejemplos: 
 

Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)

Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair

El método más simple es ejecutar dos bucles, el bucle exterior selecciona el primer elemento (elemento más pequeño) y el bucle interior busca el elemento seleccionado por el bucle exterior más n. La complejidad temporal de este método es O(n^2).
Podemos usar la clasificación y la búsqueda binaria para mejorar la complejidad del tiempo a O (nLogn). El primer paso es ordenar la array en orden ascendente. Una vez que la array esté ordenada, recorra la array de izquierda a derecha, y para cada elemento arr[i], busque binariamente arr[i] + n en arr[i+1..n-1]. Si se encuentra el elemento, devuelve el par. 
Tanto el primer como el segundo paso toman O (nLogn). Entonces, la complejidad general es O (nLogn). 
El segundo paso del algoritmo anterior se puede mejorar a O(n). El primer paso sigue siendo el mismo. La idea para el segundo paso es tomar dos variables de índice i y j, inicializarlas como 0 y 1 respectivamente. Ahora ejecute un bucle lineal. Si arr[j] – arr[i] es más pequeño que n, debemos buscar un arr[j] mayor, por lo tanto, incremente j. Si arr[j] – arr[i] es mayor que n, debemos buscar un arr[i] mayor, por lo tanto, incremente i. Gracias a Aashish Barnwal por sugerir este enfoque. 
El siguiente código es solo para el segundo paso del algoritmo, asume que la array ya está ordenada. 
 

// C program to find a pair with the given difference
#include <stdio.h>
 
// The function assumes that the array is sorted
bool findPair(int arr[], int size, int n)
{
    // Initialize positions of two elements
    int i = 0; 
    int j = 1;
 
    // Search for a pair
    while (i<size && j<size)
    {
        if (i != j && arr[j]-arr[i] == n)
        {
            printf("Pair Found: (%d, %d)", arr[i], arr[j]);
            return true;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
 
    printf("No such pair");
    return false;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {1, 8, 30, 40, 100};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 60;
    findPair(arr, size, n);
    return 0;
}

Producción:  

Pair Found: (40, 100)

Complejidad de tiempo: O(n)
Espacio auxiliar: O(1) El
hash también se puede utilizar para resolver este problema. Cree una tabla hash vacía HT. Recorra la array, use los elementos de la array como claves hash e ingréselos en HT. Atraviese la array nuevamente y busque el valor n + arr[i] en HT. 
 

¡ Consulte el artículo completo sobre Encuentre un par con la diferencia dada para obtener más detalles!