Cuente todos los pares disjuntos que tengan una diferencia absoluta de al menos K de una array dada

Dada una array arr[] que consta de N enteros, la tarea es contar todos los pares disjuntos que tengan una diferencia absoluta de al menos K
Nota: El par (arr[i], arr[j]) y (arr[j], arr[i]) se consideran como el mismo par.

Ejemplos:

Entrada: arr[] = {1, 3, 3, 5}, K = 2
Salida: 2
Explicación:
Los siguientes dos pares satisfacen las condiciones necesarias: 

  • {arr[0], arr[1]} = (1, 3) cuya diferencia absoluta es |1 – 3| = 2
  • {arr[2], arr[3]} = (3, 5) cuya diferencia absoluta es |3 – 5| = 2

Entrada: arr[] = {1, 2, 3, 4}, K = 3
Salida: 1
Explicación:
El único par que cumple las condiciones necesarias es {arr[0], arr[3]} = (1, 4), desde |1 – 4| = 3.

Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles de la array dada y contar aquellos pares cuya diferencia absoluta es al menos K y realizar un seguimiento de los elementos que ya se han tomado en pares, utilizando una array auxiliar visited[] para marcar los elementos emparejados.

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 count distinct pairs
// with absolute difference atleast K
void countPairsWithDiffK(int arr[],
                         int N, int K)
{
    // Track the element that
    // have been paired
    int vis[N];
    memset(vis, 0, sizeof(vis));
 
    // Stores count of distinct pairs
    int count = 0;
 
    // Pick all elements one by one
    for (int i = 0; i < N; i++) {
 
        // If already visited
        if (vis[i] == 1)
            continue;
 
        for (int j = i + 1; j < N; j++) {
 
            // If already visited
            if (vis[j] == 1)
                continue;
 
            // If difference is at least K
            if (abs(arr[i] - arr[j]) >= K) {
 
                // Mark element as visited and
                // increment the count
                count++;
                vis[i] = 1;
                vis[j] = 1;
                break;
            }
        }
    }
 
    // Print the final count
    cout << count << ' ';
}
 
// Driver Code
int main()
{
    // Given arr[]
    int arr[] = { 1, 3, 3, 5 };
 
    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given difference K
    int K = 2;
 
    // Function Call
    countPairsWithDiffK(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
  
// Function to count distinct pairs
// with absolute difference atleast K
static void countPairsWithDiffK(int arr[],
                                int N, int K)
{
     
    // Track the element that
    // have been paired
    int []vis = new int[N];
    Arrays.fill(vis, 0);
     
    // Stores count of distinct pairs
    int count = 0;
 
    // Pick all elements one by one
    for(int i = 0; i < N; i++)
    {
         
        // If already visited
        if (vis[i] == 1)
            continue;
 
        for(int j = i + 1; j < N; j++)
        {
             
            // If already visited
            if (vis[j] == 1)
                continue;
 
            // If difference is at least K
            if (Math.abs(arr[i] - arr[j]) >= K)
            {
                 
                // Mark element as visited and
                // increment the count
                count++;
                vis[i] = 1;
                vis[j] = 1;
                break;
            }
        }
    }
 
    // Print the final count
    System.out.print(count);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given arr[]
    int arr[] = { 1, 3, 3, 5 };
 
    // Size of array
    int N = arr.length;
 
    // Given difference K
    int K = 2;
 
    // Function Call
    countPairsWithDiffK(arr, N, K);
}
}
 
// This code is contributed by bgangwar59

Python3

# Python3 program for the above approach
 
# Function to count distinct pairs
# with absolute difference atleast K
def countPairsWithDiffK(arr, N, K):
     
    # Track the element that
    # have been paired
    vis = [0] * N
     
    # Stores count of distinct pairs
    count = 0
 
    # Pick all elements one by one
    for i in range(N):
         
        # If already visited
        if (vis[i] == 1):
            continue
 
        for j in range(i + 1, N):
             
            # If already visited
            if (vis[j] == 1):
                continue
 
            # If difference is at least K
            if (abs(arr[i] - arr[j]) >= K):
 
                # Mark element as visited and
                # increment the count
                count += 1
                vis[i] = 1
                vis[j] = 1
                break
 
    # Print the final count
    print(count)
 
# Driver Code
if __name__ == '__main__':
     
    # Given arr[]
    arr = [ 1, 3, 3, 5 ]
 
    # Size of array
    N = len(arr)
     
    # Given difference K
    K = 2
 
    # Function Call
    countPairsWithDiffK(arr, N, K)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count distinct pairs
// with absolute difference atleast K
static void countPairsWithDiffK(int[] arr, int N,
                                int K)
{
     
    // Track the element that
    // have been paired
    int[] vis = new int[N];
 
    // Stores count of distinct pairs
    int count = 0;
 
    // Pick all elements one by one
    for(int i = 0; i < N; i++)
    {
         
        // If already visited
        if (vis[i] == 1)
            continue;
             
        for(int j = i + 1; j < N; j++)
        {
             
            // If already visited
            if (vis[j] == 1)
                continue;
 
            // If difference is at least K
            if (Math.Abs(arr[i] - arr[j]) >= K)
            {
                 
                // Mark element as visited and
                // increment the count
                count++;
                vis[i] = 1;
                vis[j] = 1;
                break;
            }
        }
    }
 
    // Print the final count
    Console.Write(count);
}
 
// Driver Code
public static void Main()
{
     
    // Given arr[]
    int[] arr = { 1, 3, 3, 5 };
 
    // Size of array
    int N = arr.Length;
 
    // Given difference K
    int K = 2;
 
    // Function Call
    countPairsWithDiffK(arr, N, K);
}
}
 
// This code is contributed by chitranayal

Javascript

<script>
 
// JavaScript implementation
// for above approach
 
// Function to count distinct pairs
// with absolute difference atleast K
function countPairsWithDiffK(arr, N, K)
{
    // Track the element that
    // have been paired
    var vis = new Array(N);
    vis.fill(0);
 
    // Stores count of distinct pairs
    var count = 0;
 
    // Pick all elements one by one
    for (var i = 0; i < N; i++) {
 
        // If already visited
        if (vis[i] == 1)
            continue;
 
        for (var j = i + 1; j < N; j++) {
 
            // If already visited
            if (vis[j] == 1)
                continue;
 
            // If difference is at least K
            if (Math.abs(arr[i] - arr[j]) >= K) {
 
                // Mark element as visited and
                // increment the count
                count++;
                vis[i] = 1;
                vis[j] = 1;
                break;
            }
        }
    }
 
    // Print the final count
    document.write( count + " ");
}
 
    var arr = [ 1, 3, 3, 5 ];
 
    // Size of array
    var N = arr.length;
 
    // Given difference K
    var K = 2;
 
    // Function Call
    countPairsWithDiffK(arr, N, K);
 
 
// This code is contributed by SoumikMondal
 
</script>
Producción

2 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea eficiente es usar la búsqueda binaria para encontrar la primera ocurrencia que tenga una diferencia de al menos K . A continuación se muestran los pasos:

  • Ordena la array dada en orden creciente .
  • Inicialice cnt a 0 , lo que almacenará el recuento de todos los pares posibles.
  • Realice la búsqueda binaria según lo siguiente:
    • Inicialice la izquierda como 0 y la derecha como N/2 + 1 .
    • Encuentre el valor de mid como (izquierda + derecha) / 2 .
    • Compruebe si se puede formar un número medio de pares emparejando los elementos M más a la izquierda con los elementos M más a la derecha , es decir, compruebe si arr[0] – arr[N – M] ≥ d, arr[1] – arr[N -M + 1] ≥ re, …, arr[M – 1] – arr[N – 1] ≥ re .
    • En los pasos anteriores, recorra la array en el rango [0, M] y, si existe un índice cuyo abs (arr [N – M + i] – arr [i]) sea menor que K , actualice a la derecha como (mid – 1) .
    • De lo contrario, actualice left como mid + 1 y cnt como mid .
  • Después del paso anterior, imprima el valor de cnt como todos los recuentos posibles de pares.

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 check if it is possible to
// form M pairs with abs diff at least K
bool isValid(int arr[], int n, int m,
             int d)
{
    // Traverse the array over [0, M]
    for (int i = 0; i < m; i++) {
 
        // If valid index
        if (abs(arr[n - m + i]
                - arr[i])
            < d) {
            return 0;
        }
    }
 
    // Return 1
    return 1;
}
 
// Function to count distinct pairs
// with absolute difference atleasr K
int countPairs(int arr[], int N, int K)
{
    // Stores the count of all
    // possible pairs
    int ans = 0;
 
    // Initialize left and right
    int left = 0, right = N / 2 + 1;
 
    // Sort the array
    sort(arr, arr + N);
 
    // Perform Binary Search
    while (left < right) {
 
        // Find the value of mid
        int mid = (left + right) / 2;
 
        // Check valid index
        if (isValid(arr, N, mid, K)) {
 
            // Update ans
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    // Print the answer
    cout << ans << ' ';
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 3, 3, 5 };
 
    // Given difference K
    int K = 2;
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    countPairs(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
  
// Function to check if it is possible to
// form M pairs with abs diff at least K
static int isValid(int arr[], int n, int m,
                   int d)
{
     
    // Traverse the array over [0, M]
    for(int i = 0; i < m; i++)
    {
         
        // If valid index
        if (Math.abs(arr[n - m + i] - arr[i]) < d)
        {
            return 0;
        }
    }
 
    // Return 1
    return 1;
}
 
// Function to count distinct pairs
// with absolute difference atleasr K
static void countPairs(int arr[], int N, int K)
{
     
    // Stores the count of all
    // possible pairs
    int ans = 0;
 
    // Initialize left and right
    int left = 0, right = N / 2 + 1;
 
    // Sort the array
    Arrays.sort(arr);
 
    // Perform Binary Search
    while (left < right)
    {
         
        // Find the value of mid
        int mid = (left + right) / 2;
 
        // Check valid index
        if (isValid(arr, N, mid, K) == 1)
        {
             
            // Update ans
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    // Print the answer
    System.out.print(ans);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given array arr[]
    int arr[] = { 1, 3, 3, 5 };
 
    // Given difference K
    int K = 2;
 
    // Size of the array
    int N = arr.length;
 
    // Function call
    countPairs(arr, N, K);
}
}
 
// This code is contributed by bgangwar59

Python3

# Python3 program for the above approach
 
# Function to check if it is possible to
# form M pairs with abs diff at least K
def isValid(arr, n, m, d):
     
    # Traverse the array over [0, M]
    for i in range(m):
         
        # If valid index
        if (abs(arr[n - m + i] - arr[i]) < d):
            return 0
 
    # Return 1
    return 1
 
# Function to count distinct pairs
# with absolute difference atleasr K
def countPairs(arr, N, K):
     
    # Stores the count of all
    # possible pairs
    ans = 0
 
    # Initialize left and right
    left = 0
    right = N // 2 + 1
 
    # Sort the array
    arr.sort(reverse = False)
 
    # Perform Binary Search
    while (left < right):
         
        # Find the value of mid
        mid = (left + right) // 2
 
        # Check valid index
        if (isValid(arr, N, mid, K)):
             
            # Update ans
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
 
    # Print the answer
    print(ans, end = "")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 1, 3, 3, 5 ]
 
    # Given difference K
    K = 2
 
    # Size of the array
    N = len(arr)
 
    # Function call
    countPairs(arr, N, K)
 
# This code is contributed by bgangwar59

C#

// C# program for the
// above approach
using System;
class GFG{
  
// Function to check if it
// is possible to form M
// pairs with abs diff at
// least K
static int isValid(int []arr, int n,
                   int m, int d)
{   
  // Traverse the array over
  // [0, M]
  for(int i = 0; i < m; i++)
  {
    // If valid index
    if (Math.Abs(arr[n - m + i] -
                 arr[i]) < d)
    {
      return 0;
    }
  }
 
  // Return 1
  return 1;
}
 
// Function to count distinct
// pairs with absolute difference
// atleast K
static void countPairs(int []arr,
                       int N, int K)
{   
  // Stores the count of all
  // possible pairs
  int ans = 0;
 
  // Initialize left
  // and right
  int left = 0,
      right = N / 2 + 1;
 
  // Sort the array
  Array.Sort(arr);
 
  // Perform Binary Search
  while (left < right)
  {
    // Find the value of mid
    int mid = (left +
               right) / 2;
 
    // Check valid index
    if (isValid(arr, N,
                mid, K) == 1)
    {
      // Update ans
      ans = mid;
      left = mid + 1;
    }
    else
      right = mid - 1;
  }
 
  // Print the answer
  Console.WriteLine(ans);
}
 
// Driver Code
public static void Main()
{   
  // Given array arr[]
  int []arr = {1, 3, 3, 5};
 
  // Given difference K
  int K = 2;
 
  // Size of the array
  int N = arr.Length;
 
  // Function call
  countPairs(arr, N, K);
}
}
 
// This code is contributed by surendra_gangwar

Javascript

<script>
// javascript program for the above approach
 
    // Function to check if it is possible to
    // form M pairs with abs diff at least K
    function isValid(arr , n , m , d) {
 
        // Traverse the array over [0, M]
        for (i = 0; i < m; i++) {
 
            // If valid index
            if (Math.abs(arr[n - m + i] - arr[i]) < d) {
                return 0;
            }
        }
 
        // Return 1
        return 1;
    }
 
    // Function to count distinct pairs
    // with absolute difference atleasr K
    function countPairs(arr , N , K) {
 
        // Stores the count of all
        // possible pairs
        var ans = 0;
 
        // Initialize left and right
        var left = 0, right = N / 2 + 1;
 
        // Sort the array
        arr.sort();
 
        // Perform Binary Search
        while (left < right) {
 
            // Find the value of mid
            var mid = parseInt((left + right) / 2);
 
            // Check valid index
            if (isValid(arr, N, mid, K) == 1) {
 
                // Update ans
                ans = mid;
                left = mid + 1;
            } else
                right = mid - 1;
        }
 
        // Print the answer
        document.write(ans);
    }
 
    // Driver Code
     
 
        // Given array arr
        var arr = [ 1, 3, 3, 5 ];
 
        // Given difference K
        var K = 2;
 
        // Size of the array
        var N = arr.length;
 
        // Function call
        countPairs(arr, N, K);
 
// This code contributed by gauravrajput1
</script>
Producción

2 

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por pankajsharma_ 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 *