Encuentra un par con la diferencia dada

Posted on by Rudeus Greyrat

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: 

Entrada: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Salida: Par encontrado: (2, 80)

Entrada: arr[] = {90, 70, 20, 80, 50}, n = 45
Salida: No existe tal par

Método 1: 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 ).

Método 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). 
Método 3:El segundo paso del Método -2 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 e 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++

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
 
// 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 || arr[i] - arr[j] == n) )
        {
            cout << "Pair Found: (" << arr[i] <<
                        ", " << arr[j] << ")";
            return true;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
 
    cout << "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;
}
 
// This is code is contributed by rathbhupendra

C

// C program to find a pair with the given difference
#include <stdio.h>
 
// The function assumes that the array is sorted
int 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 || arr[i] - arr[j] == n))
        {
            printf("Pair Found: (%d, %d)", arr[i], arr[j]);
            return 1;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
 
    printf("No such pair");
    return 0;
}
 
// 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;
}

Java

// Java program to find a pair with the given difference
import java.io.*;
 
class PairDifference
{
    // The function assumes that the array is sorted
    static boolean findPair(int arr[],int n)
    {
        int size = arr.length;
 
        // Initialize positions of two elements
        int i = 0, j = 1;
 
        // Search for a pair
        while (i < size && j < size)
        {
            if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n))
            {
                System.out.print("Pair Found: "+
                                 "( "+arr[i]+", "+ arr[j]+" )");
                return true;
            }
            else if (arr[j] - arr[i] < n)
                j++;
            else
                i++;
        }
 
        System.out.print("No such pair");
        return false;
    }
 
    // Driver program to test above function
    public static void main (String[] args)
    {
        int arr[] = {1, 8, 30, 40, 100};
        int n = -60;
        findPair(arr,n);
    }
}
/*This code is contributed by Devesh Agrawal*/

Python

# Python program to find a pair with the given difference
 
# The function assumes that the array is sorted
def findPair(arr,n):
 
    size = len(arr)
 
    # Initialize positions of two elements
    i,j = 0,1
 
    # Search for a pair
    while i < size and j < size:
 
        if i != j and arr[j]-arr[i] == n:
            print "Pair found (",arr[i],",",arr[j],")"
            return True
 
        elif arr[j] - arr[i] < n:
            j+=1
        else:
            i+=1
    print "No pair found"
    return False
 
# Driver function to test above function
arr = [1, 8, 30, 40, 100]
n = 60
findPair(arr, n)
 
# This code is contributed by Devesh Agrawal

C#

// C# program to find a pair with the given difference
using System;
 
class GFG {
     
    // The function assumes that the array is sorted
    static bool findPair(int []arr, int n)
    {
        int size = arr.Length;
 
        // Initialize positions of two elements
        int i = 0, j = 1;
 
        // Search for a pair
        while (i < size && j < size)
        {
            if (i != j && arr[j] - arr[i] == n)
            {
                Console.Write("Pair Found: "
                + "( " + arr[i] + ", " + arr[j] +" )");
                 
                return true;
            }
            else if (arr[j] - arr[i] < n)
                j++;
            else
                i++;
        }
 
        Console.Write("No such pair");
         
        return false;
    }
 
    // Driver program to test above function
    public static void Main()
    {
        int []arr = {1, 8, 30, 40, 100};
        int n = 60;
         
        findPair(arr, n);
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP program to find a pair with
// the given difference
 
// The function assumes that the
// array is sorted
function findPair(&$arr, $size, $n)
{
    // Initialize positions of
    // two elements
    $i = 0;
    $j = 1;
 
    // Search for a pair
    while ($i < $size && $j < $size)
    {
        if ($i != $j && $arr[$j] -
                        $arr[$i] == $n)
        {
            echo "Pair Found: " . "(" .
                  $arr[$i] . ", " . $arr[$j] . ")";
            return true;
        }
        else if ($arr[$j] - $arr[$i] < $n)
            $j++;
        else
            $i++;
    }
 
    echo "No such pair";
    return false;
}
 
// Driver Code
$arr = array(1, 8, 30, 40, 100);
$size = sizeof($arr);
$n = 60;
findPair($arr, $size, $n);
 
// This code is contributed
// by ChitraNayal
?>

JavaScript

<script>
 
       // JavaScript program for the above approach
 
       // The function assumes that the array is sorted
       function findPair(arr, size, n) {
           // Initialize positions of two elements
           let i = 0;
           let j = 1;
 
           // Search for a pair
           while (i < size && j < size) {
               if (i != j && arr[j] - arr[i] == n) {
                   document.write("Pair Found: (" + arr[i] + ", " +
                   arr[j] + ")");
                   return true;
               }
               else if (arr[j] - arr[i] < n)
                   j++;
               else
                   i++;
           }
 
           document.write("No such pair");
           return false;
       }
 
       // Driver program to test above function
 
       let arr = [1, 8, 30, 40, 100];
       let size = arr.length;
       let n = 60;
       findPair(arr, size, n);
 
 
   // This code is contributed by Potta Lokesh
  
   </script>
Producción

Pair Found: (100, 40)

Complejidad de tiempo: O(n*log(n)) [Aún se requiere clasificar como primer paso], donde n es el número de elementos en una array dada
Espacio auxiliar: O(1)

El código anterior se puede simplificar y se puede hacer más comprensible al reducir el montón de comprobaciones If-Else. Gracias a Nakshatra Chhillar por sugerir esta simplificación. Entenderemos las simplificaciones a través del siguiente código:

C++

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
bool findPair(int arr[], int size, int n)
{
    // Step-1 Sort the array
    sort(arr, arr + size);
 
    // Initialize positions of two elements
    int l = 0;
    int r = 1;
 
    // take absolute value of difference
    // this does not affect the pair as A-B=diff is same as
    // B-A= -diff
    n = abs(n);
 
    // Search for a pair
 
    // These roop running conditions are sufficient
    while (l <= r and r < size) {
        int diff = arr[r] - arr[l];
        if (diff == n
            and l != r) // we need distinct elements in pair
                        // so l!=r
        {
            cout << "Pair Found: (" << arr[l] << ", "
                 << arr[r] << ")";
            return true;
        }
        else if (diff > n) // try to reduce the diff
            l++;
        else // Note if l==r then r will be advanced thus no
             // pair will be missed
            r++;
    }
    cout << "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);
    cout << endl;
    n = 20;
    findPair(arr, size, n);
    return 0;
}
 
// This code is contributed by Nakshatra Chhillar
Producción

Pair Found: (40, 100)
No such pair

Complejidad de tiempo: O(n*log(n)) [Aún se requiere clasificar como primer paso], donde n es el número de elementos en una array dada
Espacio auxiliar: O(1)

Método 4: también se puede usar hash 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. 

C++

// C++ program to find a pair with the given difference
#include <bits/stdc++.h>
using namespace std;
 
// The function assumes that the array is sorted
bool findPair(int arr[], int size, int n)
{
    unordered_map<int, int> mpp;
    for (int i = 0; i < size; i++) {
        mpp[arr[i]]++;
 
        // Check if any element whose frequency
        // is greater than 1 exist or not for n == 0
        if (n == 0 && mpp[arr[i]] > 1)
            return true;
    }
 
    // Check if difference is zero and
    // we are unable to find any duplicate or
    // element whose frequency is greater than 1
    // then no such pair found.
    if (n == 0)
        return false;
 
    for (int i = 0; i < size; i++) {
        if (mpp.find(n + arr[i]) != mpp.end()) {
            cout << "Pair Found: (" << arr[i] << ", "
                 << n + arr[i] << ")";
            return true;
        }
    }
 
    cout << "No Pair found";
    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;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // The function assumes that the array is sorted
  static boolean findPair(int[] arr, int size, int n)
  {
    HashMap<Integer,
            Integer> mpp = new HashMap<Integer,
                                      Integer>();
 
     // Traverse the array
    for(int i = 0; i < size; i++)
    {
          
        // Update frequency
        // of arr[i]
        mpp.put(arr[i],
               mpp.getOrDefault(arr[i], 0) + 1);
       
        // Check if any element whose frequency
        // is greater than 1 exist or not for n == 0
        if (n == 0 && mpp.get(arr[i]) > 1)
            return true;
    }
  
     // Check if difference is zero and
    // we are unable to find any duplicate or
    // element whose frequency is greater than 1
    // then no such pair found.
    if (n == 0)
        return false;
 
    for (int i = 0; i < size; i++) {
      if (mpp.containsKey(n + arr[i])) {
        System.out.print("Pair Found: (" + arr[i] + ", " +
                      + (n + arr[i]) + ")");
        return true;
      }
    }
    System.out.print("No Pair found");
    return false;
  }
 
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 1, 8, 30, 40, 100 };
    int size = arr.length;
    int n = -60;
    findPair(arr, size, n);
}
}
 
// This code is contributed by code_hunt.

Python3

# Python program to find a pair with the given difference
 
# The function assumes that the array is sorted
def findPair(arr, size, n):
 
    mpp = {}
 
    for i in range(size):
        if arr[i] in mpp.keys():
             mpp[arr[i]] += 1
             if(n == 0 and mpp[arr[i]] > 1):
                return true;
        else:
             mpp[arr[i]] = 1
     
    if(n == 0):
      return false;
 
    for i in range(size):
         if n + arr[i] in mpp.keys():
            print("Pair Found: (" + str(arr[i]) + ", " + str(n + arr[i]) + ")")
            return True
     
    print("No Pair found")
    return False
 
# Driver program to test above function
arr = [ 1, 8, 30, 40, 100 ]
size = len(arr)
n = -60
findPair(arr, size, n)
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// The function assumes that the array is sorted
static bool findPair(int[] arr, int size, int n)
{
    Dictionary<int, int> mpp = new Dictionary<int, int>();
 
    // Traverse the array
    for(int i = 0; i < size; i++)
    {
         
        // Update frequency
        // of arr[i]
        mpp[arr[i]]=mpp.GetValueOrDefault(arr[i], 0) + 1;
     
        // Check if any element whose frequency
        // is greater than 1 exist or not for n == 0
        if (n == 0 && mpp[arr[i]] > 1)
            return true;
    }
 
    // Check if difference is zero and
    // we are unable to find any duplicate or
    // element whose frequency is greater than 1
    // then no such pair found.
    if (n == 0)
        return false;
 
    for (int i = 0; i < size; i++) {
    if (mpp.ContainsKey(n + arr[i])) {
        Console.WriteLine("Pair Found: (" + arr[i] + ", " +
                    + (n + arr[i]) + ")");
        return true;
    }
    }
    Console.WriteLine("No Pair found");
    return false;
}
 
// Driver Code
public static void Main(string []args)
{
    int[] arr = { 1, 8, 30, 40, 100 };
    int size = arr.Length;
    int n = -60;
    findPair(arr, size, n);
}
}
 
// This code is contributed by Aman Kumar

JavaScript

<script>
// Javascript program for the above approach
 
// The function assumes that the array is sorted
function findPair(arr, size, n) {
  let mpp = new Map();
 
  // Traverse the array
  for (let i = 0; i < size; i++) {
 
    // Update frequency
    // of arr[i]
    if (mpp.has(arr[i]))
      mpp.set(arr[i], mpp.get(arr[i]) + 1);
    else
      mpp.set(arr[i], 1)
 
    // Check if any element whose frequency
    // is greater than 1 exist or not for n == 0
    if (n == 0 && mpp.get(arr[i]) > 1)
      return true;
  }
 
  // Check if difference is zero and
  // we are unable to find any duplicate or
  // element whose frequency is greater than 1
  // then no such pair found.
  if (n == 0)
    return false;
 
  for (let i = 0; i < size; i++) {
    if (mpp.has(n + arr[i])) {
      document.write("Pair Found: (" + arr[i] + ", " +
        + (n + arr[i]) + ")");
      return true;
    }
  }
  document.write("No Pair found");
  return false;
}
 
// Driver Code
let arr = [1, 8, 30, 40, 100];
let size = arr.length;
let n = -60;
findPair(arr, size, n);
 
// This code is contributed by Saurabh Jaiswal
</script>
Producción

Pair Found: (100, 40)

Complejidad de tiempo: O(n), donde n es el número de elementos en una array dada
Espacio auxiliar: O(n)
 

Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto o encuentra otras formas de resolver el mismo problema.
 

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 *