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