Dada una array de enteros y un entero positivo k, cuente todos los pares distintos con diferencias iguales a k.
Ejemplos:
Input: arr[] = {1, 5, 3, 4, 2}, k = 3
Output: 2
There are 2 pairs with difference 3, the pairs are {1, 4} and {5, 2}
Input: arr[] = {8, 12, 16, 4, 0, 20}, k = 4
Output: 5
There are 5 pairs with difference 4, the pairs are {0, 4}, {4, 8},
{8, 12}, {12, 16} and {16, 20}
Método 1 (simple):
una solución simple es considerar todos los pares uno por uno y verificar la diferencia entre cada par. El siguiente programa implementa la solución simple. Ejecutamos dos bucles: el bucle exterior elige el primer elemento del par, el bucle interior busca el otro elemento. Esta solución no funciona si hay duplicados en la array, ya que el requisito es contar solo pares distintos.
C++
/* A simple program to count pairs with difference k*/
#include <iostream>
using namespace std;
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
// Pick all elements one by one
for (int i = 0; i < n; i++) {
// See if there is a pair of this picked element
for (int j = i + 1; j < n; j++)
if (arr[i] - arr[j] == k
|| arr[j] - arr[i] == k)
count++;
}
return count;
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 5, 3, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
/* A simple program to count pairs with difference k*/
#include <stdio.h>
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
// Pick all elements one by one
for (int i = 0; i < n; i++) {
// See if there is a pair of this picked element
for (int j = i + 1; j < n; j++)
if (arr[i] - arr[j] == k
|| arr[j] - arr[i] == k)
count++;
}
return count;
}
// Driver program to test above function
int main()
{
int arr[] = { 1, 5, 3, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printf("Count of pairs with given diff is %d",
countPairsWithDiffK(arr, n, k));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// A simple Java program to
//count pairs with difference k
import java.util.*;
import java.io.*;
class GFG {
static int countPairsWithDiffK(int arr[],
int n, int k)
{
int count = 0;
// Pick all elements one by one
for (int i = 0; i < n; i++)
{
// See if there is a pair
// of this picked element
for (int j = i + 1; j < n; j++)
if (arr[i] - arr[j] == k ||
arr[j] - arr[i] == k)
count++;
}
return count;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 5, 3, 4, 2 };
int n = arr.length;
int k = 3;
System.out.println("Count of pairs with given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed
// by Sahil_Bansall
Python3
# A simple program to count pairs with difference k
def countPairsWithDiffK(arr, n, k):
count = 0
# Pick all elements one by one
for i in range(0, n):
# See if there is a pair of this picked element
for j in range(i+1, n) :
if arr[i] - arr[j] == k or arr[j] - arr[i] == k:
count += 1
return count
# Driver program
arr = [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print ("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
C#
// A simple C# program to count pairs with
// difference k
using System;
class GFG {
static int countPairsWithDiffK(int []arr,
int n, int k)
{
int count = 0;
// Pick all elements one by one
for (int i = 0; i < n; i++)
{
// See if there is a pair
// of this picked element
for (int j = i + 1; j < n; j++)
if (arr[i] - arr[j] == k ||
arr[j] - arr[i] == k)
count++;
}
return count;
}
// Driver code
public static void Main()
{
int []arr = { 1, 5, 3, 4, 2 };
int n = arr.Length;
int k = 3;
Console.WriteLine("Count of pairs with "
+ " given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A simple PHP program to count
// pairs with difference k
function countPairsWithDiffK($arr, $n,
$k)
{
$count = 0;
// Pick all elements one by one
for($i = 0; $i < $n; $i++)
{
// See if there is a pair of
// this picked element
for($j = $i + 1; $j < $n; $j++)
if ($arr[$i] - $arr[$j] == $k or
$arr[$j] - $arr[$i] == $k)
$count++;
}
return $count;
}
// Driver Code
$arr = array(1, 5, 3, 4, 2);
$n = count($arr);
$k = 3;
echo "Count of pairs with given diff is "
, countPairsWithDiffK($arr, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
/* A simple program to count pairs
with difference k*/
function countPairsWithDiffK(arr, n, k)
{
count = 0;
// Pick all elements one by one
for (let i = 0; i < n; i++)
{
// See if there is a pair of this
// picked element
for (let j = i+1; j < n; j++)
if (arr[i] - arr[j] == k ||
arr[j] - arr[i] == k )
count++;
}
return count;
}
// Driver program to test above function
arr =new Array(1, 5, 3, 4, 2);
n = arr.length;
k = 3;
document.write("Count of pairs with given diff is "
+ countPairsWithDiffK(arr, n, k));
// This code is contributed by simranarora5sos
</script>
Producción
Count of pairs with given diff is 2
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (Usar clasificación)
Podemos encontrar el conteo en tiempo O(nLogn) usando un algoritmo de clasificación O(nLogn) como Merge Sort , Heap Sort , etc. Los siguientes son los pasos detallados.
1) Initialize count as 0 2) Sort all numbers in increasing order. 3) Remove duplicates from array. 4) Do following for each element arr[i] a) Binary Search for arr[i] + k in subarray from i+1 to n-1. b) If arr[i] + k found, increment count. 5) Return count.
C++
/* A sorting based program to count pairs with difference k*/
#include <iostream>
#include <algorithm>
using namespace std;
/* Standard binary search function */
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low)
{
int mid = low + (high - low)/2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid -1), x);
}
return -1;
}
/* Returns count of pairs with difference k in arr[] of size n. */
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0, i;
sort(arr, arr+n); // Sort array elements
/* code to remove duplicates from arr[] */
// Pick a first element point
for (i = 0; i < n-1; i++)
if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1)
count++;
return count;
}
// Driver program
int main()
{
int arr[] = {1, 5, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
Java
// A sorting base java program to
// count pairs with difference k
import java.util.*;
import java.io.*;
class GFG {
// Standard binary search function //
static int binarySearch(int arr[], int low,
int high, int x)
{
if (high >= low)
{
int mid = low + (high - low) / 2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1),
high, x);
else
return binarySearch(arr, low,
(mid - 1), x);
}
return -1;
}
// Returns count of pairs with
// difference k in arr[] of size n.
static int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0, i;
// Sort array elements
Arrays.sort(arr);
// code to remove duplicates from arr[]
// Pick a first element point
for (i = 0; i < n - 1; i++)
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1)
count++;
return count;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 5, 3, 4, 2 };
int n = arr.length;
int k = 3;
System.out.println("Count of pairs with given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed by Sahil_Bansall
Python
# A sorting based program to
# count pairs with difference k
# Standard binary search function
def binarySearch(arr, low, high, x):
if (high >= low):
mid = low + (high - low)//2
if x == arr[mid]:
return (mid)
elif(x > arr[mid]):
return binarySearch(arr, (mid + 1), high, x)
else:
return binarySearch(arr, low, (mid -1), x)
return -1
# Returns count of pairs with
# difference k in arr[] of size n.
def countPairsWithDiffK(arr, n, k):
count = 0
arr.sort() # Sort array elements
# code to remove
# duplicates from arr[]
# Pick a first element point
for i in range (0, n - 2):
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1):
count += 1
return count
# Driver Code
arr= [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print ("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
# This code is contributed
# by Shivi_Aggarwal
C#
// A sorting base C# program to
// count pairs with difference k
using System;
class GFG {
// Standard binary search function
static int binarySearch(int []arr, int low,
int high, int x)
{
if (high >= low)
{
int mid = low + (high - low) / 2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1),
high, x);
else
return binarySearch(arr, low,
(mid - 1), x);
}
return -1;
}
// Returns count of pairs with
// difference k in arr[] of size n.
static int countPairsWithDiffK(int []arr,
int n, int k)
{
int count = 0, i;
// Sort array elements
Array.Sort(arr);
// code to remove duplicates from arr[]
// Pick a first element point
for (i = 0; i < n - 1; i++)
if (binarySearch(arr, i + 1, n - 1,
arr[i] + k) != -1)
count++;
return count;
}
// Driver code
public static void Main()
{
int []arr = { 1, 5, 3, 4, 2 };
int n = arr.Length;
int k = 3;
Console.WriteLine("Count of pairs with"
+ " given diff is "
+ countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// A sorting based PHP program to
// count pairs with difference k
// Standard binary search function
function binarySearch($arr, $low,
$high, $x)
{
if ($high >= $low)
{
$mid = $low + ($high - $low)/2;
if ($x == $arr[$mid])
return $mid;
if ($x > $arr[$mid])
return binarySearch($arr, ($mid + 1),
$high, $x);
else
return binarySearch($arr, $low,
($mid -1), $x);
}
return -1;
}
/* Returns count of pairs with
difference k in arr[] of size n. */
function countPairsWithDiffK($arr, $n, $k)
{
$count = 0;
$i;
// Sort array elements
sort($arr);
// Code to remove duplicates
// from arr[]
// Pick a first element point
for ($i = 0; $i < $n - 1; $i++)
if (binarySearch($arr, $i + 1, $n - 1,
$arr[$i] + $k) != -1)
$count++;
return $count;
}
// Driver Code
$arr = array(1, 5, 3, 4, 2);
$n = count($arr);
$k = 3;
echo "Count of pairs with given diff is "
, countPairsWithDiffK($arr, $n, $k);
// This code is contributed by anuj-67.
?>
Javascript
<script>
/* A sorting based program to count
pairs with difference k*/
/* Standard binary search function */
function binarySearch(arr, low, high, x)
{
if (high >= low)
{
let mid = low + Math.floor((high - low)/2);
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid -1), x);
}
return -1;
}
/* Returns count of pairs with difference
k in arr[] of size n. */
function countPairsWithDiffK(arr, n, k)
{
let count = 0, i;
// Sort array elements
arr.sort((a, b) => a - b);
/* code to remove duplicates from arr[] */
// Pick a first element point
for (i = 0; i < n-1; i++)
if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1)
count++;
return count;
}
// Driver program
let arr = [1, 5, 3, 4, 2];
let n = arr.length;
let k = 3;
document.write("Count of pairs with given diff is "
+ countPairsWithDiffK(arr, n, k));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
Count of pairs with given diff is 2
El primer paso (ordenar) toma tiempo O(nLogn). El segundo paso ejecuta la búsqueda binaria n veces, por lo que la complejidad temporal del segundo paso también es O(nLogn). Por lo tanto, la complejidad temporal total es O(nLogn). El segundo paso se puede optimizar a O (n), vea esto .
Complejidad de tiempo: O(nlogn)
Espacio auxiliar: O(1)
Método 3 (Usar BST de autoequilibrio) :
También podemos usar un BST autoequilibrado como el árbol AVL o el árbol Red Black para resolver este problema. A continuación se muestra un algoritmo detallado.
1) Initialize count as 0. 2) Insert all elements of arr[] in an AVL tree. While inserting, ignore an element if already present in AVL tree. 3) Do following for each element arr[i]. a) Search for arr[i] + k in AVL tree, if found then increment count. b) Search for arr[i] - k in AVL tree, if found then increment count. c) Remove arr[i] from AVL tree.
La complejidad de tiempo de la solución anterior también es O(nLogn) ya que las operaciones de búsqueda y eliminación toman tiempo O(Logn) para un árbol de búsqueda binaria autoequilibrado.
Método 4 (usar hashing):
también podemos usar hashing para lograr la complejidad de tiempo promedio como O(n) para muchos casos.
1) Initialize count as 0. 2) Insert all distinct elements of arr[] in a hash map. While inserting, ignore an element if already present in the hash map. 3) Do following for each element arr[i]. a) Look for arr[i] + k in the hash map, if found then increment count. b) Look for arr[i] - k in the hash map, if found then increment count. c) Remove arr[i] from hash table.
Un caso muy simple en el que el hashing funciona en tiempo O(n) es el caso en el que un rango de valores es muy pequeño. Por ejemplo, en la siguiente implementación, se supone que el rango de números es de 0 a 99999. Se puede usar una técnica de hash simple para usar valores como índice.
C++
/* An efficient program to count pairs with difference k when the range
numbers is small */
#define MAX 100000
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0; // Initialize count
// Initialize empty hashmap.
bool hashmap[MAX] = {false};
// Insert array elements to hashmap
for (int i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (int i = 0; i < n; i++)
{
int x = arr[i];
if (x - k >= 0 && hashmap[x - k])
count++;
if (x + k < MAX && hashmap[x + k])
count++;
hashmap[x] = false;
}
return count;
}
Java
/* An efficient program to count pairs with difference k when the range
numbers is small */
static int MAX=100000;
public static int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0; // Initialize count
// Initialize empty hashmap.
boolean hashmap[MAX] = {false};
// Insert array elements to hashmap
for (int i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (int i = 0; i < n; i++)
{
int x = arr[i];
if (x - k >= 0 && hashmap[x - k])
count++;
if (x + k < MAX && hashmap[x + k])
count++;
hashmap[x] = false;
}
return count;
}
// This code is contributed by RohitOberoi.
Python3
''' An efficient program to count pairs with difference k when the range numbers is small ''' MAX = 100000; def countPairsWithDiffK(arr, n, k): count = 0; # Initialize count # Initialize empty hashmap. hashmap = [False for i in range(MAX)]; # Insert array elements to hashmap for i in range(n): hashmap[arr[i]] = True; for i in range(n): x = arr[i]; if (x - k >= 0 and hashmap[x - k]): count+=1; if (x + k < MAX and hashmap[x + k]): count+=1; hashmap[x] = False; return count; # This code is contributed by 29AjayKumar
C#
/* An efficient program to count pairs with difference k when the range
numbers is small */
static int MAX=100000;
public static int countPairsWithDiffK(int []arr, int n, int k)
{
int count = 0; // Initialize count
// Initialize empty hashmap.
bool hashmap[MAX] = {false};
// Insert array elements to hashmap
for (int i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (int i = 0; i < n; i++)
{
int x = arr[i];
if (x - k >= 0 && hashmap[x - k])
count++;
if (x + k < MAX && hashmap[x + k])
count++;
hashmap[x] = false;
}
return count;
}
// This code is contributed by famously.
Javascript
<script>
/* An efficient program to count pairs with difference k when the range
numbers is small */
var MAX = 100000;
function countPairsWithDiffK(arr, n, k)
{
var count = 0; // Initialize count
// Initialize empty hashmap.
var hashmap = Array(MAX).fill(false);
// Insert array elements to hashmap
for (var i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (var i = 0; i < n; i++)
{
var x = arr[i];
if (x - k >= 0 && hashmap[x - k])
count++;
if (x + k < MAX && hashmap[x + k])
count++;
hashmap[x] = false;
}
return count;
}
</script>
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 5 (Uso de clasificación) :
- Ordenar la array arr
- Tome dos punteros, l y r, ambos apuntando al primer elemento
- Toma la diferencia arr[r] – arr[l]
- Si la diferencia de valor es K, incremente el conteo y mueva ambos punteros al siguiente elemento
- si el valor diff > k, mueve l al siguiente elemento
- si el valor diff < k, mueve r al siguiente elemento
- recuento de retorno
C++
/* A sorting based program to count pairs with difference k*/
#include <iostream>
#include <algorithm>
using namespace std;
/* Returns count of pairs with difference k in arr[] of size n. */
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
sort(arr, arr+n); // Sort array elements
int l = 0;
int r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else // arr[r] - arr[l] < sum
r++;
}
return count;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 5, 3, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
Java
// A sorting based Java program to
// count pairs with difference k
import java.util.*;
class GFG {
/* Returns count of pairs with
difference k in arr[] of size n. */
static int countPairsWithDiffK(int arr[], int n,
int k)
{
int count = 0;
Arrays.sort(arr); // Sort array elements
int l = 0;
int r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else // arr[r] - arr[l] < sum
r++;
}
return count;
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = {1, 5, 3, 4, 2};
int n = arr.length;
int k = 3;
System.out.println("Count of pairs with given diff is " +
countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed by Prerna Saini
Python3
# A sorting based program to
# count pairs with difference k
def countPairsWithDiffK(arr,n,k):
count =0
# Sort array elements
arr.sort()
l =0
r=0
while r<n:
if arr[r]-arr[l]==k:
count+=1
l+=1
r+=1
# arr[r] - arr[l] < sum
elif arr[r]-arr[l]>k:
l+=1
else:
r+=1
return count
# Driver code
if __name__=='__main__':
arr = [1, 5, 3, 4, 2]
n = len(arr)
k = 3
print("Count of pairs with given diff is ",
countPairsWithDiffK(arr, n, k))
# This code is contributed by
# Shrikant13
C#
// A sorting based C# program to count
// pairs with difference k
using System;
class GFG {
/* Returns count of pairs with
difference k in arr[] of size n. */
static int countPairsWithDiffK(int []arr,
int n, int k)
{
int count = 0;
// Sort array elements
Array.Sort(arr);
int l = 0;
int r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else // arr[r] - arr[l] < sum
r++;
}
return count;
}
// Driver program to test above function
public static void Main()
{
int []arr = {1, 5, 3, 4, 2};
int n = arr.Length;
int k = 3;
Console.Write("Count of pairs with "
+ "given diff is " +
countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A sorting based program to count
// pairs with difference k
// Returns count of pairs with
// difference k in arr[] of size n.
function countPairsWithDiffK( $arr, $n, $k)
{
$count = 0;
// Sort array elements
sort($arr);
$l = 0;
$r = 0;
while($r < $n)
{
if($arr[$r] - $arr[$l] == $k)
{
$count++;
$l++;
$r++;
}
else if($arr[$r] - $arr[$l] > $k)
$l++;
// arr[r] - arr[l] < k
else
$r++;
}
return $count;
}
// Driver Code
$arr = array(1, 5, 3, 4, 2);
$n =count($arr);
$k = 3;
echo "Count of pairs with given diff is "
, countPairsWithDiffK($arr, $n, $k);
// This code is contributed by anuj_67,
?>
Javascript
<script>
// Javascript program to
// count pairs with difference k
/* Returns count of pairs with
difference k in arr[] of size n. */
function countPairsWithDiffK(arr, n, k)
{
let count = 0;
arr.sort(); // Sort array elements
let l = 0;
let r = 0;
while(r < n)
{
if(arr[r] - arr[l] == k)
{
count++;
l++;
r++;
}
else if(arr[r] - arr[l] > k)
l++;
else // arr[r] - arr[l] < sum
r++;
}
return count;
}
// Driver program
let arr = [1, 5, 3, 4, 2];
let n = arr.length;
let k = 3;
document.write("Count of pairs with given diff is " +
countPairsWithDiffK(arr, n, k));
</script>
Producción
Count of pairs with given diff is 2
Complejidad de tiempo : O(nlogn)
Espacio auxiliar : O(1)
Método 6 (usando la búsqueda binaria) (funciona con duplicados en la array):
1) Inicializar la cuenta como 0.
2) Ordena todos los números en orden creciente.
4) Haz lo siguiente para cada elemento arr[i]
a) Búsqueda binaria de la primera aparición de arr[i] + k en el subarreglo arr[i+1, N-1], deje que este índice sea ‘X’.
b) Si no se encuentra arr[i] + k, devolver el índice de la primera aparición del valor mayor que arr[i] + k.
c ) Repita los pasos ayb para buscar la primera aparición de arr[i] + k + 1, sea este índice ‘Y’.
d) Incremente la cuenta con ‘Y – X’.
5) Cuenta de retorno.
C++
#include <bits/stdc++.h>
using namespace std;
int BS(int arr[], int X, int low, int N)
{
int high = N - 1;
int ans = N;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] >= X) {
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
int countPairsWithDiffK(int arr[], int N, int k)
{
int count = 0;
sort(arr, arr + N);
for (int i = 0; i < N; ++i) {
int X = BS(arr, arr[i] + k, i + 1, N);
if (X != N) {
int Y = BS(arr, arr[i] + k + 1, i + 1, N);
count += Y - X;
}
}
return count;
}
int main()
{
int arr[] = { 1, 3, 5, 8, 6, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << "Count of pairs with given diff is "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
// This code is contributed by umadevi9616
Java
import java.io.*;
class GFG {
static int BS(int[] arr, int X, int low) {
int high = arr.length - 1;
int ans = arr.length;
while(low <= high) {
int mid = low + (high - low) / 2;
if(arr[mid] >= X) {
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
return ans;
}
static int countPairsWithDiffK(int[] arr, int N, int k) {
int count = 0;
Arrays.sort(arr);
for(int i = 0 ; i < N ; ++i) {
int X = BS(arr, arr[i] + k, i + 1);
if(X != N) {
int Y = BS(arr, arr[i] + k + 1, i + 1);
count += Y - X;
}
}
return count;
}
public static void main (String[] args) {
int arr[] = {1, 3, 5, 8, 6, 4, 6};
int n = arr.length;
int k = 2;
System.out.println("Count of pairs with given diff is " +
countPairsWithDiffK(arr, n, k));
}
}
Python3
def BS(arr, X, low):
high = len(arr) - 1;
ans = len(arr);
while (low <= high):
mid = low + (high - low) // 2;
if (arr[mid] >= X):
ans = mid;
high = mid - 1;
else:
low = mid + 1;
return ans;
def countPairsWithDiffK(arr, N, k):
count = 0;
arr.sort();
for i in range(N):
X = BS(arr, arr[i] + k, i + 1);
if (X != N):
Y = BS(arr, arr[i] + k + 1, i + 1);
count += Y - X;
return count;
if __name__ == '__main__':
arr = [ 1, 3, 5, 8, 6, 4, 6 ];
n = len(arr);
k = 2;
print("Count of pairs with given diff is " , countPairsWithDiffK(arr, n, k));
# This code is contributed by shikhasingrajput
C#
using System;
class GFG{
static int BS(int[] arr, int X, int low)
{
int high = arr.Length - 1;
int ans = arr.Length;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] >= X)
{
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
return ans;
}
static int countPairsWithDiffK(int[] arr, int N, int k)
{
int count = 0;
Array.Sort(arr);
for(int i = 0 ; i < N ; ++i)
{
int X = BS(arr, arr[i] + k, i + 1);
if (X != N)
{
int Y = BS(arr, arr[i] + k + 1, i + 1);
count += Y - X;
}
}
return count;
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 1, 3, 5, 8, 6, 4, 6 };
int n = arr.Length;
int k = 2;
Console.WriteLine("Count of pairs with given diff is " +
countPairsWithDiffK(arr, n, k));
}
}
// This code is contributed by ukasp
Javascript
<script>
function BS(arr, X, low)
{
let high = arr.length - 1;
let ans = arr.length;
while(low <= high)
{
let mid = low + (high - low) / 2;
if (arr[mid] >= X)
{
ans = mid;
high = mid - 1;
}
else low = mid + 1;
}
return ans;
}
function countPairsWithDiffK(arr, N, k)
{
let count = 2;
arr.sort();
for(let i = 0 ; i < N ; ++i)
{
let X = BS(arr, arr[i] + k, i + 1);
if (X != N)
{
let Y = BS(arr, arr[i] + k + 1,
i + 1);
count += Y - X;
}
}
return count;
}
// Driver code
let arr = [ 1, 3, 5, 8, 6, 4, 6 ];
let n = arr.length;
let k = 3;
document.write("Count of pairs with given diff is " +
countPairsWithDiffK(arr, n, k));
// This code is contributed by shivanisinghss2110
</script>
Producción
Count of pairs with given diff is 6
Complejidad de tiempo: O(nlogn)
Espacio auxiliar: O(1)
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