C++
// C++ code to find no. of subsets with
// maximum difference d between max and
#include <bits/stdc++.h>
using namespace std;
// function to calculate factorial of a numb
int fact(int i)
{
if (i == 0)
return 1;
return i * fact(i - 1);
}
int ans(int a[], int n, int k, int x)
{
if (k > n || n < 1)
return 0;
sort(a, a + n);
int count = 0;
int j = 1;
int i = 0;
int kfactorial = fact(k);
while (j <= n) {
while (j < n && a[j] - a[i] <= x) {
j++;
}
if ((j - i) >= k) {
count = count
+ fact(j - i)
/ (kfactorial * fact(j - i - k));
}
else {
i++;
j++;
continue;
}
if (j == n)
break;
while (i < j && a[j] - a[i] > x) {
i++;
}
if ((j - i) >= k) {
count = count
- fact(j - i)
/ (kfactorial * fact(j - i - k));
}
}
return count;
}
// driver program to test the above
// function
int main()
{
int arr[] = { 1, 12, 9, 2, 4, 2, 5, 8, 4, 6 },
k = 3,x = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << ans(arr, n, k, x);
return 0;
}
// This code is contributed by Vishakha Chauhan
Producción
52
Dada una array y dos enteros k y d, encuentre el número de subconjuntos de esta array de tamaño k, donde la diferencia entre el número máximo y mínimo del subconjunto es como máximo d.
Ejemplos:
Input : a[] = [5, 4, 2, 1, 3],
k = 3, d = 5
Output : 10
Explanation:
{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5},
{1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}.
We can see each subset has atmost
difference d=5 between the minimum
and maximum element of each subset.
No of such subsets = 10
Input : a[] = [1, 2, 3, 4, 5, 6],
k = 3, d = 5
Output : 20
Enfoque ingenuo : encontrar todos los subconjuntos de tamaño k y para cada subconjunto encontrar la diferencia entre el elemento máximo y mínimo. Si la diferencia es menor o igual a d, cuéntalos.
Enfoque eficiente :
- Clasificación : primero ordene la array en orden creciente. Ahora, supongamos que queremos averiguar para cada i -ésimo elemento, el número de subconjuntos requeridos en los que el entero a[i] está presente como el elemento mínimo de ese subconjunto. El máximo en tal subconjunto nunca excederá a[i] + d .
- Encontrar el índice máximo j : Podemos aplicar la búsqueda binaria sobre esta array para cada i, para encontrar el índice máximo j, tal que a[j] <= a[i]+d. Ahora, cualquier subconjunto que incluya a[i] y cualquier otro elemento del rango i+1…j será un subconjunto requerido porque el elemento a[i] es el mínimo de ese subconjunto, y la diferencia entre cualquier otro elemento y a[ i] es siempre menor que igual a d.
- Aplique la fórmula básica de combinatoria : ahora queremos encontrar el número de subconjuntos requeridos de tamaño k. Esto será mediante el uso de la fórmula básica de combinación cuando tenga que seleccionar r elementos de n números dados. De la misma manera, debemos elegir (k-1) números de (ji) elementos que ya incluyen a[i], que es el número mínimo en cada subconjunto. La suma de este procedimiento para cada i -ésimo elemento será la respuesta final.
Aquí he usado una forma recursiva simple para encontrar factorial de un número, uno también puede usar programación dinámica para encontrarlo.
Ilustración :
Entrada: a = [5, 4, 2, 1, 3],
k = 3, d = 5
Salida: 10Explicación:
array ordenada en orden ascendente: [1, 2, 3, 4, 5]
Para a[0] = 1 como elemento mínimo, el
número de subconjunto será 6, que son {1, 2, 3}, {1, 2 , 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}.
Para a[1] = 2 como elemento mínimo, el
número de subconjunto será 3, que son {2, 3, 4}, {2, 3, 5}, {2, 4, 5}
Para a[2] = 3 como elemento mínimo
El número de subconjunto será 1, que es {3, 4, 5}
No se formará ningún otro subconjunto de tamaño k = 3
tomando a[3] = 4 o a[4] = 5 como elemento mínimo
C++
// C++ code to find no. of subsets with
// maximum difference d between max and
// min of all K-size subsets function to
// calculate factorial of a number
#include <bits/stdc++.h>
using namespace std;
int fact (int n){
if (n==0)
return 1;
else
return n * fact(n-1);
}
// function to count ways to select r
// numbers from n given numbers
int findcombination (int n,int r){
return( fact(n) / (fact(n - r) *
fact(r)));
}
// function to return the total number
// of required subsets :
// n is the number of elements in array
// d is the maximum difference between
// minimum and maximum element in each
// subset of size k
int find(int arr[], int n, int d, int k)
{
sort(arr,arr+n);
int ans = 0, end = n, co = 0,
start = 0;
// loop to traverse from 0-n
for (int i = 0; i < n; i++) {
int val = arr[i] + d;
// binary search to get the position
// which will be stored in start
start = i;
while (start < end - 1){
int mid = (start + end) / 2;
// if mid value greater than
// arr[i]+d do search in
// arr[start:mid]
if (arr[mid] > val)
end = mid;
else
start = mid + 1;
}
if (start != n and arr[start]
<= val)
start += 1;
int c = start-i;
// if the numbers of elements 'c'
// is greater or equal to the given
// size k, then only subsets of
// required size k can be formed
if (c >= k){
co += findcombination(c - 1, k - 1);}
}
return co;
}
// driver program to test the above
// function
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6},
k = 3, d = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << find(arr, n,d,k);
return 0;
}
// This code is contributed by Prerna Saini
Java
// Java code to find no. of subsets
// with maximum difference d between
// max and min of all K-size subsets
import java.util.*;
class GFG {
// function to calculate factorial
// of a number
static int fact (int n){
if (n==0)
return 1;
else
return n * fact(n-1);
}
// function to count ways to select r
// numbers from n given numbers
static int findcombination(int n, int r){
return( fact(n) / (fact(n - r) *
fact(r)));
}
// function to return the total number
// of required subsets :
// n is the number of elements in array
// d is the maximum difference between
// minimum and maximum element in each
// subset of size k
static int find(int arr[], int n, int d,
int k)
{
Arrays.sort(arr);
int ans = 0, end = n, co = 0,
start = 0;
// loop to traverse from 0-n
for (int i = 0; i < n; i++) {
int val = arr[i] + d;
// binary search to get the position
// which will be stored in start
start=i;
while (start < end - 1){
int mid = (start + end) / 2;
// if mid value greater than
// arr[i]+d do search in
// arr[start:mid]
if (arr[mid] > val)
end = mid;
else
start = mid+1;
}
if (start !=n && arr[start] <= val)
start += 1;
int c = start-i;
// if the numbers of elements 'c' is
// greater or equal to the given size k,
// then only subsets of required size k
// can be formed
if (c >= k){
co += findcombination(c - 1, k - 1);}
}
return co;
}
// driver program to test the above function
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6}, k = 3,
d = 5;
int n = arr.length;
System.out.println(find(arr, n,d,k));
}
}
// This code is contributed by Prerna Saini
Python
# Python code to find no. of subsets with maximum # difference d between max and min of all K-size # subsets function to calculate factorial of a # number def fact (n): if (n==0): return (1) else: return n * fact(n-1) # function to count ways to select r numbers # from n given numbers def findcombination (n,r): return( fact(n)//(fact(n-r)*fact(r))) # function to return the total number of required # subsets : # n is the number of elements in list l[0..n-1] # d is the maximum difference between minimum and # maximum element in each subset of size k def find (a, n, d, k): # sort the list first in ascending order a.sort() (start, end, co) = (0, n, 0) for i in range(0, n): val = a[i]+ d # binary search to get the position # which will be stored in start # such that a[start] <= a[i]+d start = i while (start< end-1): mid = (start+end)//2 # if mid value greater than a[i]+d # do search in l[start:mid] if (a[mid] > val): end = mid # if mid value less or equal to a[i]+d # do search in a[mid+1:end] else: start = mid+1 if (start!=n and a[start]<=val): start += 1 # count the numbers of elements that fall # in range i to start c = start-i # if the numbers of elements 'c' is greater # or equal to the given size k, then only # subsets of required size k can be formed if (c >= k): co += findcombination(c-1,k-1) return co # Driver code n = 6 # Number of elements d = 5 # maximum diff k = 3 # Size of subsets print(find([1, 2, 3, 4, 5, 6], n, d, k))
C#
// C# code to find no. of subsets
// with maximum difference d between
// max and min of all K-size subsets
using System;
class GFG {
// function to calculate factorial
// of a number
static int fact (int n)
{
if (n == 0)
return 1;
else
return n * fact(n - 1);
}
// function to count ways to select r
// numbers from n given numbers
static int findcombination(int n, int r)
{
return( fact(n) / (fact(n - r) *
fact(r)));
}
// function to return the total number
// of required subsets :
// n is the number of elements in array
// d is the maximum difference between
// minimum and maximum element in each
// subset of size k
static int find(int []arr, int n, int d,
int k)
{
Array.Sort(arr);
//int ans = 0,
int end = n, co = 0,
start = 0;
// loop to traverse from 0-n
for (int i = 0; i < n; i++)
{
int val = arr[i] + d;
// binary search to get the
// position which will be
// stored in start
start = i;
while (start < end - 1){
int mid = (start + end) / 2;
// if mid value greater than
// arr[i]+d do search in
// arr[start:mid]
if (arr[mid] > val)
end = mid;
else
start = mid+1;
}
if (start !=n && arr[start] <= val)
start += 1;
int c = start-i;
// if the numbers of elements 'c' is
// greater or equal to the given size k,
// then only subsets of required size k
// can be formed
if (c >= k)
co += findcombination(c - 1, k - 1);
}
return co;
}
// driver program to test the above function
public static void Main()
{
int []arr = {1, 2, 3, 4, 5, 6};
int k = 3;
int d = 5;
int n = arr.Length;
Console.WriteLine(find(arr, n, d, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// Php code to find no. of subsets with
// maximum difference d between max and
// min of all K-size subsets function to
// calculate factorial of a number
function fact ($n){
if ($n==0)
return 1;
else
return $n * fact($n-1);
}
// function to count ways to select r
// numbers from n given numbers
function findcombination ($n,$r){
return( fact($n) / (fact($n - $r) *
fact($r)));
}
// function to return the total number
// of required subsets :
// n is the number of elements in array
// d is the maximum difference between
// minimum and maximum element in each
// subset of size k
function find(&$arr, $n, $d, $k)
{
sort($arr);
$ans = 0;
$end = $n;
$co = 0;
$start = 0;
// loop to traverse from 0-n
for ($i = 0; $i < $n; $i++) {
$val = $arr[$i] + $d;
// binary search to get the position
// which will be stored in start
$start = $i;
while ($start < $end - 1){
$mid = intval (($start + $end) / 2);
// if mid value greater than
// arr[i]+d do search in
// arr[start:mid]
if ($arr[$mid] > $val)
$end = $mid;
else
$start = $mid + 1;
}
if ($start != $n && $arr[$start]
<= $val)
$start += 1;
$c = $start-$i;
// if the numbers of elements 'c'
// is greater or equal to the given
// size k, then only subsets of
// required size k can be formed
if ($c >= $k){
$co += findcombination($c - 1, $k - 1);}
}
return $co;
}
// driver program to test the above
// function
$arr = array(1, 2, 3, 4, 5, 6);
$k = 3;
$d = 5;
$n = sizeof($arr) / sizeof($arr[0]);
echo find($arr, $n,$d,$k);
return 0;
?>
Javascript
<script>
// Javascript code to find no. of subsets
// with maximum difference d between
// max and min of all K-size subsets
// function to calculate factorial
// of a number
function fact(n)
{
let answer=1;
if (n == 0 || n == 1)
{ return answer;}
else
{
for(var i = n; i >= 1; i--){
answer = answer * i;
}
return answer;
}
}
// function to count ways to select r
// numbers from n given numbers
function findcombination(n,r)
{
return( Math.floor(fact(n) / (fact(n - r) *
fact(r))));
}
// function to return the total number
// of required subsets :
// n is the number of elements in array
// d is the maximum difference between
// minimum and maximum element in each
// subset of size k
function find(arr, n, d, k)
{
arr.sort(function(a, b){return a-b;});
let ans = 0, end = n, co = 0,
start = 0;
// loop to traverse from 0-n
for (let i = 0; i < n; i++) {
let val = arr[i] + d;
// binary search to get the position
// which will be stored in start
start=i;
while (start < end - 1){
let mid = Math.floor((start + end) / 2);
// if mid value greater than
// arr[i]+d do search in
// arr[start:mid]
if (arr[mid] > val)
end = mid;
else
start = mid+1;
}
if (start !=n && arr[start] <= val)
start += 1;
let c = start-i;
// if the numbers of elements 'c' is
// greater or equal to the given size k,
// then only subsets of required size k
// can be formed
if (c >= k){
co += findcombination(c - 1, k - 1);}
}
return co;
}
// driver program to test the above function
let arr = [1, 2, 3, 4, 5, 6];
let k = 3, d = 5;
let n = arr.length;
document.write(find(arr, n, d, k));
// This code is contributed by rag2127.
</script>
Producción
20
Complejidad de tiempo: O(N logN) , donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1) , no se requiere espacio adicional, por lo que es una constante.
Este artículo es una contribución de Sruti Rai . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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