Dado un conjunto de n puntos distintos x 1 , x 2 , x 3 … x n todos sobre el eje X y un número entero L, la tarea es encontrar el número de formas de seleccionar tres puntos tales que la distancia entre los más los puntos distantes son menores o iguales a L
Nota : el orden no es importante, es decir, los puntos {3, 2, 1} y {1, 2, 3} representan el mismo conjunto de tres puntos
Ejemplos:
Entrada: x = {1, 2, 3, 4}
L = 3
Salida: 4
Explicación: Las
formas de seleccionar tres puntos de manera que la distancia entre
los puntos más distantes <= L son:
1) {1, 2, 3} Aquí distancia entre puntos más lejanos = 3 – 1 = 2 <= L
2) {1, 2, 4} Aquí distancia entre puntos más lejanos = 4 – 1 = 3 <= L
3) {1, 3, 4} Aquí distancia entre puntos más lejanos = 4 – 1 = 3 <= L
4) {2, 3, 4} Aquí la distancia entre los puntos más lejanos = 4 – 2 = 2 <= L
Por lo tanto, el número total de caminos = 4
Enfoque ingenuo:
en primer lugar, ordene la array de puntos para generar tripletes {a, b, c} de modo que a y c sean los puntos más alejados del triplete y a < b < c, ya que todos los puntos son distintos. Podemos generar todos los tripletes posibles y verificar la condición si la distancia entre los dos puntos más distantes en <= L. Si se cumple, contamos de esta manera, de lo contrario, no
C++
// C++ program to count ways to choose
// triplets such that the distance
// between the farthest points <= L
#include<bits/stdc++.h>
using namespace std;
// Returns the number of triplets with
// distance between farthest points <= L
int countTripletsLessThanL(int n, int L, int* arr)
{
// sort to get ordered triplets so that we can
// find the distance between farthest points
// belonging to a triplet
sort(arr, arr + n);
int ways = 0;
// generate and check for all possible
// triplets: {arr[i], arr[j], arr[k]}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// Since the array is sorted the
// farthest points will be a[i]
// and a[k];
int mostDistantDistance = arr[k] - arr[i];
if (mostDistantDistance <= L) {
ways++;
}
}
}
}
return ways;
}
// Driver Code
int main()
{
// set of n points on the X axis
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int L = 3;
int ans = countTripletsLessThanL(n, L, arr);
cout << "Total Number of ways = " << ans << "\n";
return 0;
}
Java
// Java program to count ways to choose
// triplets such that the distance
// between the farthest points <= L
import java .io.*;
import java .util.Arrays;
class GFG {
// Returns the number of triplets with
// distance between farthest points <= L
static int countTripletsLessThanL(int n, int L,
int []arr)
{
// sort to get ordered triplets
// so that we can find the
// distance between farthest
// points belonging to a triplet
Arrays.sort(arr);
int ways = 0;
// generate and check for all possible
// triplets: {arr[i], arr[j], arr[k]}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// Since the array is sorted the
// farthest points will be a[i]
// and a[k];
int mostDistantDistance =
arr[k] - arr[i];
if (mostDistantDistance <= L)
{
ways++;
}
}
}
}
return ways;
}
// Driver Code
static public void main (String[] args)
{
// set of n points on the X axis
int []arr = {1, 2, 3, 4};
int n =arr.length;
int L = 3;
int ans = countTripletsLessThanL(n, L, arr);
System.out.println("Total Number of ways = "
+ ans);
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to count ways to choose
# triplets such that the distance
# between the farthest points <= L
# Returns the number of triplets with
# distance between farthest points <= L
def countTripletsLessThanL(n, L, arr):
# sort to get ordered triplets so that
# we can find the distance between
# farthest points belonging to a triplet
arr.sort()
ways = 0
# generate and check for all possible
# triplets: {arr[i], arr[j], arr[k]}
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
# Since the array is sorted the
# farthest points will be a[i]
# and a[k];
mostDistantDistance = arr[k] - arr[i]
if (mostDistantDistance <= L):
ways += 1
return ways
# Driver Code
if __name__ == "__main__":
# set of n points on the X axis
arr = [1, 2, 3, 4 ]
n = len(arr)
L = 3
ans = countTripletsLessThanL(n, L, arr)
print ("Total Number of ways =", ans)
# This code is contributed by ita_c
C#
// C# program to count ways to choose
// triplets such that the distance
// between the farthest points <= L
using System;
class GFG {
// Returns the number of triplets with
// distance between farthest points <= L
static int countTripletsLessThanL(int n, int L,
int []arr)
{
// sort to get ordered triplets
// so that we can find the
// distance between farthest
// points belonging to a triplet
Array.Sort(arr);
int ways = 0;
// generate and check for all possible
// triplets: {arr[i], arr[j], arr[k]}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// Since the array is sorted the
// farthest points will be a[i]
// and a[k];
int mostDistantDistance = arr[k] - arr[i];
if (mostDistantDistance <= L)
{
ways++;
}
}
}
}
return ways;
}
// Driver Code
static public void Main ()
{
// set of n points on the X axis
int []arr = {1, 2, 3, 4};
int n =arr.Length;
int L = 3;
int ans = countTripletsLessThanL(n, L, arr);
Console.WriteLine("Total Number of ways = " + ans);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to count ways to choose
// triplets such that the distance
// between the farthest points <= L
// Returns the number of triplets with
// distance between farthest points <= L
function countTripletsLessThanL($n, $L, $arr)
{
// sort to get ordered triplets so that
// we can find the distance between
// farthest points belonging to a triplet
sort($arr);
$ways = 0;
// generate and check for all possible
// triplets: {arr[i], arr[j], arr[k]}
for ($i = 0; $i < $n; $i++)
{
for ($j = $i + 1; $j < $n; $j++)
{
for ($k = $j + 1; $k < $n; $k++)
{
// Since the array is sorted the
// farthest points will be a[i]
// and a[k];
$mostDistantDistance = $arr[$k] -
$arr[$i];
if ($mostDistantDistance <= $L)
{
$ways++;
}
}
}
}
return $ways;
}
// Driver Code
// set of n points on the X axis
$arr = array( 1, 2, 3, 4 );
$n = sizeof($arr);
$L = 3;
$ans = countTripletsLessThanL($n, $L, $arr);
echo "Total Number of ways = " , $ans, "\n";
// This code is contributed by akt_mit
?>
Javascript
<script>
// javascript program to count ways to choose
// triplets such that the distance
// between the farthest points <= L
// Returns the number of triplets with
// distance between farthest points <= L
function countTripletsLessThanL(n , L, arr)
{
// sort to get ordered triplets
// so that we can find the
// distance between farthest
// points belonging to a triplet
arr.sort();
var ways = 0;
// generate and check for all possible
// triplets: {arr[i], arr[j], arr[k]}
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
for (k = j + 1; k < n; k++) {
// Since the array is sorted the
// farthest points will be a[i]
// and a[k];
var mostDistantDistance = arr[k] - arr[i];
if (mostDistantDistance <= L) {
ways++;
}
}
}
}
return ways;
}
// Driver Code
// set of n points on the X axis
var arr = [ 1, 2, 3, 4 ];
var n = arr.length;
var L = 3;
var ans = countTripletsLessThanL(n, L, arr);
document.write("Total Number of ways = " + ans);
// This code contributed by Rajput-Ji
</script>
Producción:
Total Number of ways = 4
Complejidad temporal: O(n 3 ) para generar todos los tripletes posibles.
Enfoque eficiente:
- Este problema se puede resolver utilizando la búsqueda binaria.
- En primer lugar, ordene la array.
- Ahora, para cada elemento de la array encontramos el número de elementos que son mayores que él (manteniendo un orden ordenado de puntos) y se encuentran en el rango (x i + 1, x i + L) ambos inclusive (Observe que aquí todos los puntos son distintos por lo que necesitamos considerar los elementos iguales a x i mismo).
- Al hacerlo, encontramos todos aquellos puntos donde la distancia entre los puntos más lejanos siempre será menor o igual a L.
- Ahora digamos que para el i -ésimo punto, tenemos M puntos que son menores o iguales a x i + L, entonces el número de formas en que podemos seleccionar 2 puntos de M tales puntos es simplemente
M * (M – 1) / 2
C++
// C++ program to count ways to choose
// triplets such that the distance between
// the farthest points <= L */
#include<bits/stdc++.h>
using namespace std;
// Returns the number of triplets with the
// distance between farthest points <= L
int countTripletsLessThanL(int n, int L, int* arr)
{
// sort the array
sort(arr, arr + n);
int ways = 0;
for (int i = 0; i < n; i++) {
// find index of element greater than arr[i] + L
int indexGreater = upper_bound(arr, arr + n,
arr[i] + L) - arr;
// find Number of elements between the ith
// index and indexGreater since the Numbers
// are sorted and the elements are distinct
// from the points btw these indices represent
// points within range (a[i] + 1 and a[i] + L)
// both inclusive
int numberOfElements = indexGreater - (i + 1);
// if there are at least two elements in between
// i and indexGreater find the Number of ways
// to select two points out of these
if (numberOfElements >= 2) {
ways += (numberOfElements
* (numberOfElements - 1) / 2);
}
}
return ways;
}
// Driver Code
int main()
{
// set of n points on the X axis
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int L = 4;
int ans = countTripletsLessThanL(n, L, arr);
cout << "Total Number of ways = " << ans << "\n";
return 0;
}
Java
// Java program to count ways to choose
// triplets such that the distance between
// the farthest points <= L */
import java.util.*;
class GFG
{
// Returns the number of triplets with the
// distance between farthest points <= L
static int countTripletsLessThanL(int n, int L,
int[] arr)
{
// sort the array
Arrays.sort(arr);
int ways = 0;
for (int i = 0; i < n; i++)
{
// find index of element greater than arr[i] + L
int indexGreater = upper_bound(arr, 0, n,
arr[i] + L);
// find Number of elements between the ith
// index and indexGreater since the Numbers
// are sorted and the elements are distinct
// from the points btw these indices represent
// points within range (a[i] + 1 and a[i] + L)
// both inclusive
int numberOfElements = indexGreater - (i + 1);
// if there are at least two elements in between
// i and indexGreater find the Number of ways
// to select two points out of these
if (numberOfElements >= 2)
{
ways += (numberOfElements *
(numberOfElements - 1) / 2);
}
}
return ways;
}
static int upper_bound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
public static void main(String[] args)
{
// set of n points on the X axis
int arr[] = { 1, 2, 3, 4 };
int n = arr.length;
int L = 4;
int ans = countTripletsLessThanL(n, L, arr);
System.out.println("Total Number of ways = " + ans);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program to count ways to choose
# triplets such that the distance between
# the farthest points <= L '''
# Returns the number of triplets with the
# distance between farthest points <= L
def countTripletsLessThanL(n, L, arr):
# sort the array
arr = sorted(arr);
ways = 0;
for i in range(n):
# find index of element greater than arr[i] + L
indexGreater = upper_bound(arr, 0, n, arr[i] + L);
# find Number of elements between the ith
# index and indexGreater since the Numbers
# are sorted and the elements are distinct
# from the points btw these indices represent
# points within range (a[i] + 1 and a[i] + L)
# both inclusive
numberOfElements = indexGreater - (i + 1);
# if there are at least two elements in between
# i and indexGreater find the Number of ways
# to select two points out of these
if (numberOfElements >= 2):
ways += (numberOfElements * (numberOfElements - 1) / 2);
return ways;
def upper_bound(a, low, high, element):
while (low < high):
middle = int(low + (high - low) / 2);
if (a[middle] > element):
high = middle;
else:
low = middle + 1;
return low;
# Driver Code
if __name__ == '__main__':
# set of n points on the X axis
arr = [1, 2, 3, 4];
n = len(arr);
L = 4;
ans = countTripletsLessThanL(n, L, arr);
print("Total Number of ways = " , ans);
# This code is contributed by 29AjayKumar
C#
// C# program to count ways to choose
// triplets such that the distance between
// the farthest points <= L */
using System;
class GFG
{
// Returns the number of triplets with the
// distance between farthest points <= L
static int countTripletsLessThanL(int n, int L,
int[] arr)
{
// sort the array
Array.Sort(arr);
int ways = 0;
for (int i = 0; i < n; i++)
{
// find index of element greater than arr[i] + L
int indexGreater = upper_bound(arr, 0, n,
arr[i] + L);
// find Number of elements between the ith
// index and indexGreater since the Numbers
// are sorted and the elements are distinct
// from the points btw these indices represent
// points within range (a[i] + 1 and a[i] + L)
// both inclusive
int numberOfElements = indexGreater - (i + 1);
// if there are at least two elements in between
// i and indexGreater find the Number of ways
// to select two points out of these
if (numberOfElements >= 2)
{
ways += (numberOfElements *
(numberOfElements - 1) / 2);
}
}
return ways;
}
static int upper_bound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
public static void Main(String[] args)
{
// set of n points on the X axis
int []arr = { 1, 2, 3, 4 };
int n = arr.Length;
int L = 4;
int ans = countTripletsLessThanL(n, L, arr);
Console.WriteLine("Total Number of ways = " + ans);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to count ways to choose
// triplets such that the distance between
// the farthest points <= L
// Returns the number of triplets with the
// distance between farthest points <= L
function countTripletsLessThanL(n, L, arr)
{
// Sort the array
arr.sort(function(a, b){return a - b});
let ways = 0;
for(let i = 0; i < n; i++)
{
// Find index of element greater
// than arr[i] + L
let indexGreater = upper_bound(arr, 0, n,
arr[i] + L);
// Find Number of elements between the ith
// index and indexGreater since the Numbers
// are sorted and the elements are distinct
// from the points btw these indices represent
// points within range (a[i] + 1 and a[i] + L)
// both inclusive
let numberOfElements = indexGreater - (i + 1);
// If there are at least two elements in between
// i and indexGreater find the Number of ways
// to select two points out of these
if (numberOfElements >= 2)
{
ways += (numberOfElements *
(numberOfElements - 1) / 2);
}
}
return ways;
}
function upper_bound(a, low, high, element)
{
while(low < high)
{
let middle = low +
parseInt((high - low) / 2, 10);
if (a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver code
// Set of n points on the X axis
let arr = [ 1, 2, 3, 4 ];
let n = arr.length;
let L = 4;
let ans = countTripletsLessThanL(n, L, arr);
document.write("Total Number of ways = " + ans);
// This code is contributed by suresh07
</script>
Producción
Total Number of ways = 4
Complejidad temporal: O(NlogN) donde N es el número de puntos.