Dada una array arr[] y un entero K , la tarea es encontrar el número de pares (arr[i], arr[j]) de la array tal que |arr[i] – arr[j]| ≥ K. Tenga en cuenta que (arr[i], arr[j]) y arr[j], arr[i] se contarán solo una vez.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}, K = 2
Salida: 3
Todos los pares válidos son (1, 3), (1, 4) y (2, 4)
Entrada: arr[] = { 7, 4, 12, 56, 123}, K = 50
Salida: 5
Enfoque: ordenar la array dada. Ahora, para cada elemento arr[i] , encuentre el primer elemento a la derecha arr[j] tal que (arr[j] – arr[i]) ≥ K . Esto se debe a que después de este elemento, cada elemento cumplirá la misma condición con arr[i] a medida que se ordena la array y el recuento de elementos que formarán un par válido con arr[i] será (N – j) donde N es el tamaño de la array dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of required pairs
int count(int arr[], int n, int k)
{
// Sort the given array
sort(arr, arr + n);
// To store the required count
int cnt = 0;
int i = 0, j = 1;
while (i < n && j < n) {
// Update j such that it is always > i
j = (j <= i) ? (i + 1) : j;
// Find the first element arr[j] such that
// (arr[j] - arr[i]) >= K
// This is because after this element, all
// the elements will have absolute difference
// with arr[i] >= k and the count of
// valid pairs will be (n - j)
while (j < n && (arr[j] - arr[i]) < k)
j++;
// Update the count of valid pairs
cnt += (n - j);
// Get to the next element to repeat the steps
i++;
}
// Return the count
return cnt;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << count(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class solution
{
// Function to return the count of required pairs
static int count(int arr[], int n, int k)
{
// Sort the given array
Arrays.sort(arr);
// To store the required count
int cnt = 0;
int i = 0, j = 1;
while (i < n && j < n) {
// Update j such that it is always > i
j = (j <= i) ? (i + 1) : j;
// Find the first element arr[j] such that
// (arr[j] - arr[i]) >= K
// This is because after this element, all
// the elements will have absolute difference
// with arr[i] >= k and the count of
// valid pairs will be (n - j)
while (j < n && (arr[j] - arr[i]) < k)
j++;
// Update the count of valid pairs
cnt += (n - j);
// Get to the next element to repeat the steps
i++;
}
// Return the count
return cnt;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4 };
int n = arr.length;
int k = 2;
System.out.println(count(arr, n, k));
}
}
Python3
# Python3 implementation of the approach # Function to return the count of required pairs def count(arr, n, k) : # Sort the given array arr.sort(); # To store the required count cnt = 0; i = 0; j = 1; while (i < n and j < n) : # Update j such that it is always > i if j <= i : j = i + 1 else : j = j # Find the first element arr[j] such that # (arr[j] - arr[i]) >= K # This is because after this element, all # the elements will have absolute difference # with arr[i] >= k and the count of # valid pairs will be (n - j) while (j < n and (arr[j] - arr[i]) < k) : j += 1; # Update the count of valid pairs cnt += (n - j); # Get to the next element to repeat the steps i += 1; # Return the count return cnt; # Driver code if __name__ == "__main__" : arr = [ 1, 2, 3, 4 ]; n = len(arr); k = 2; print(count(arr, n, k)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of required pairs
static int count(int []arr, int n, int k)
{
// Sort the given array
Array.Sort(arr);
// To store the required count
int cnt = 0;
int i = 0, j = 1;
while (i < n && j < n)
{
// Update j such that it is always > i
j = (j <= i) ? (i + 1) : j;
// Find the first element arr[j] such that
// (arr[j] - arr[i]) >= K
// This is because after this element, all
// the elements will have absolute difference
// with arr[i] >= k and the count of
// valid pairs will be (n - j)
while (j < n && (arr[j] - arr[i]) < k)
j++;
// Update the count of valid pairs
cnt += (n - j);
// Get to the next element to repeat the steps
i++;
}
// Return the count
return cnt;
}
// Driver code
static public void Main ()
{
int []arr = { 1, 2, 3, 4 };
int n = arr.Length;
int k = 2;
Console.Write(count(arr, n, k));
}
}
// This code is contributed by jit_t.
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the count of required pairs
function count(arr, n, k) {
// Sort the given array
arr.sort();
// To store the required count
var cnt = 0;
var i = 0;
var j = 1;
while (i < n && j < n) {
// Update j such that it is always > i
if (j <= i)
j = i + 1
else
j = j
// Find the first element arr[j] such that
// (arr[j] - arr[i]) >= K
// This is because after this element, all
// the elements will have absolute difference
// with arr[i] >= k and the count of
// valid pairs will be (n - j)
while (j < n && (arr[j] - arr[i]) < k)
j += 1;
// Update the count of valid pairs
cnt += (n - j);
// Get to the next element to repeat the steps
i += 1;
}
// Return the count
return cnt;
}
// Driver code
var arr = [ 1, 2, 3, 4 ];
var n = arr.length;
var k = 2;
document.write(count(arr, n, k));
// This code is contributed by AnkThon
</script>
Producción:
3
Complejidad de tiempo: O(n * log n)
Espacio Auxiliar: O(1)