Dada una array A[] de n elementos y un entero k . La tarea es encontrar el número de tripletes (x, y, z), donde 0 <= x, y, z < n y x, y, z son el índice en el arreglo A[] tal que:
|A[x ] – A[y]| <= k
|A[y] – A[z]| <= k
|A[z] – A[x]| <= k
Ejemplos:
Input : A[] = { 1, 1, 2, 2, 3 }, k = 1
Output : 5
(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3),
(2, 3, 4) are the triplet whose element will
satisfy the above three condition.
Input : A[] = { 1, 2, 3 }, k = 1
Output : 0
Una solución simple es ejecutar tres bucles anidados y contar trillizos con restricciones dadas.
Una solución eficiente se basa en el hecho de que reorganizar los elementos en la array no afecta la respuesta porque, básicamente, queremos que el índice x, y, z esté en orden creciente, no A[x], A[y], A[z ] para ordenar. Supongamos que A[x] está en el índice y, A[y] en z, A[z] en x, todavía podemos elegir el triplete (x, y, z) porque la condición de diferencia entre dos elementos cualesquiera es menor k sigue en pie.
Ahora, para calcular el número de índices de triplete (x, y, z) que satisface la condición anterior, ordenaremos la array dada. Ahora, para cada elemento A[i], i >= 2, encontraremos el índice límite inferior de A[i] – k, digamos lb. Ahora, observe que todos los elementos entre el índice lb e i son menores que A[i ] y la diferencia entre dos elementos cualesquiera será menor o igual que k. Por lo tanto, el elemento en el índice i puede tratarse como índice z y podemos elegir dos elementos cualquiera de lb a i – 1. Por lo tanto, esto aumentará la cuenta del triplete en i – lb C 2 .
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to count triplets with difference less
// than k.
#include <bits/stdc++.h>
using namespace std;
// Return the lower bound i.e smallest index of
// element having value greater or equal to value
int binary_lower(int value, int arr[], int n)
{
int start = 0;
int end = n - 1;
int ans = -1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (arr[mid] >= value) {
end = mid - 1;
ans = mid;
}
else {
start = mid + 1;
}
}
return ans;
}
// Return the number of triplet indices satisfies
// the three constraints
int countTriplet(int arr[], int n, int k)
{
int count = 0;
// sort the array
sort(arr, arr + n);
// for each element from index 2 to n - 1.
for (int i = 2; i < n; i++) {
// finding the lower bound of arr[i] - k.
int cur = binary_lower(arr[i] - k, arr, n);
// If there are at least two elements between
// lower bound and current element.
if (cur <= i - 2) {
// increment the count by lb - i C 2.
count += ((i - cur) * (i - cur - 1)) / 2;
}
}
return count;
}
int main()
{
int arr[] = { 1, 1, 2, 2, 3 };
int k = 1;
int n = sizeof(arr) / sizeof(arr[0]);
cout << countTriplet(arr, n, k) << endl;
return 0;
}
Java
// Java program to count triplets
// with difference less than k.
import java.io.*;
import java .util.*;
class GFG
{
// Return the lower bound i.e
// smallest index of element
// having value greater or
// equal to value
static int binary_lower(int value,
int arr[],
int n)
{
int start = 0;
int end = n - 1;
int ans = -1;
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (arr[mid] >= value)
{
end = mid - 1;
ans = mid;
}
else
{
start = mid + 1;
}
}
return ans;
}
// Return the number of
// triplet indices satisfies
// the three constraints
static int countTriplet(int arr[],
int n, int k)
{
int count = 0;
// sort the array
Arrays.sort(arr);
// for each element from
// index 2 to n - 1.
for (int i = 2; i < n; i++)
{
// finding the lower
// bound of arr[i] - k.
int cur = binary_lower(arr[i] - k,
arr, n);
// If there are at least two
// elements between lower
// bound and current element.
if (cur <= i - 2)
{
// increment the count
// by lb - i C 2.
count += ((i - cur) *
(i - cur - 1)) / 2;
}
}
return count;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {1, 1, 2, 2, 3};
int k = 1;
int n = arr.length;
System.out.println(countTriplet(arr, n, k));
}
}
// This code is contributed by anuj_67.
Python3
# Python 3 program to count # triplets with difference less # than k. # Return the lower bound # i.e smallest index of # element having value greater # or equal to value def binary_lower(value, arr, n): start = 0 end = n - 1 ans = -1 while (start <= end) : mid = (start + end) // 2 if (arr[mid] >= value) : end = mid - 1 ans = mid else : start = mid + 1 return ans # Return the number of triplet # indices satisfies # the three constraints def countTriplet(arr, n, k): count = 0 # sort the array arr.sort() # for each element from # index 2 to n - 1. for i in range(2, n) : # finding the lower bound # of arr[i] - k. cur = (binary_lower(arr[i] - k , arr, n)) # If there are at least # two elements between # lower bound and current element. if (cur <= i - 2) : # increment the count by # lb - i C 2. count += ((i - cur) * (i - cur - 1)) // 2 return count # Driver code if __name__ == "__main__": arr = [ 1, 1, 2, 2, 3 ] k = 1 n = len(arr) print(countTriplet(arr, n, k)) # This code is contributed by # ChitraNayal
C#
// C# program to count triplets
// with difference less than k.
using System;
class GFG
{
// Return the lower bound i.e
// smallest index of element
// having value greater or
// equal to value
static int binary_lower(int value,
int []arr,
int n)
{
int start = 0;
int end = n - 1;
int ans = -1;
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (arr[mid] >= value)
{
end = mid - 1;
ans = mid;
}
else
{
start = mid + 1;
}
}
return ans;
}
// Return the number of
// triplet indices satisfies
// the three constraints
static int countTriplet(int []arr,
int n, int k)
{
int count = 0;
// sort the array
Array.Sort(arr);
// for each element from
// index 2 to n - 1.
for (int i = 2; i < n; i++)
{
// finding the lower
// bound of arr[i] - k.
int cur = binary_lower(arr[i] - k,
arr, n);
// If there are at least two
// elements between lower
// bound and current element.
if (cur <= i - 2)
{
// increment the count
// by lb - i C 2.
count += ((i - cur) *
(i - cur - 1)) / 2;
}
}
return count;
}
// Driver Code
public static void Main ()
{
int []arr = {1, 1, 2, 2, 3};
int k = 1;
int n = arr.Length;
Console.WriteLine(countTriplet(arr, n, k));
}
}
// This code is contributed by anuj_67.
Javascript
<script>
// Javascript program to count triplets with difference less
// than k.
// Return the lower bound i.e smallest index of
// element having value greater or equal to value
function binary_lower(value, arr, n)
{
var start = 0;
var end = n - 1;
var ans = -1;
var mid;
while (start <= end) {
mid = parseInt((start + end) / 2);
if (arr[mid] >= value) {
end = mid - 1;
ans = mid;
}
else {
start = mid + 1;
}
}
return ans;
}
// Return the number of triplet indices satisfies
// the three constraints
function countTriplet(arr, n, k)
{
var count = 0;
// sort the array
arr.sort((a,b)=>a-b)
// for each element from index 2 to n - 1.
for (var i = 2; i < n; i++) {
// finding the lower bound of arr[i] - k.
var cur = binary_lower(arr[i] - k, arr, n);
// If there are at least two elements between
// lower bound and current element.
if (cur <= i - 2) {
// increment the count by lb - i C 2.
count += parseInt(((i - cur) * (i - cur - 1)) / 2);
}
}
return count;
}
// Driver code
var arr = [ 1, 1, 2, 2, 3 ];
var k = 1;
var n = arr.length;
document.write( countTriplet(arr, n, k));
// This code is contributed by rrrtnx.
</script>
Producción:
5
Complejidad: O(nlogn)