Dados dos enteros positivos N y K . La tarea es encontrar el número de arrays de tamaño N que se pueden formar de manera que los elementos de la array sean números enteros positivos y la suma de los elementos sea igual a K.
Ejemplos:
Input : N = 2, K = 3 Output : 2 Explanation: [1, 2] and [2, 1] are the only arrays of size 2 whose sum is 3. Input : n = 3, k = 7 Output : 15
Prerrequisito: Estrellas y Barras
Suponga que hay K objetos idénticos que deben colocarse en N contenedores (N índices de la array) de modo que cada contenedor tenga al menos un objeto. En lugar de comenzar a colocar objetos en contenedores, comenzamos a colocar los objetos en una línea, donde el objeto del primer contenedor se tomará de la izquierda, seguido de los objetos del segundo contenedor, y así sucesivamente. Por lo tanto, la configuración se determinará una vez que se sepa cuál es el primer objeto que va al segundo contenedor, y cuál es el primer objeto que va al tercer contenedor, y así sucesivamente. Podemos indicar esto colocando barras separadoras NX 1 en algunos lugares entre dos objetos; dado que no se permite que ningún contenedor esté vacío, puede haber como máximo una barra entre un par de objetos dado. Entonces, tenemos K objetos en una línea con K – 1 espacios. Ahora tenemos que elegir N – 1 huecos para colocar barras de K – 1 huecos. Esto puede ser elegido porK – 1 C N – 1 .
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find the number of arrays of
// size N whose elements are positive integers
// and sum is K
#include <bits/stdc++.h>
using namespace std;
// Return nCr
int binomialCoeff(int n, int k)
{
int C[k + 1];
memset(C, 0, sizeof(C));
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++) {
// Compute next row of pascal triangle using
// the previous row
for (int j = min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// Return the number of array that can be
// formed of size n and sum equals to k.
int countArray(int N, int K)
{
return binomialCoeff(K - 1, N - 1);
}
// Driver Code
int main()
{
int N = 2, K = 3;
cout << countArray(N, K) << endl;
return 0;
}
Java
// Java Program to find the
// number of arrays of size
// N whose elements are positive
// integers and sum is K
import java.io.*;
class GFG
{
// Return nCr
static int binomialCoeff(int n,
int k)
{
int []C = new int[k + 1];
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++)
{
// Compute next row of pascal
// triangle using the previous row
for (int j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// Return the number of
// array that can be
// formed of size n and
// sum equals to k.
static int countArray(int N, int K)
{
return binomialCoeff(K - 1, N - 1);
}
// Driver Code
public static void main (String[] args)
{
int N = 2, K = 3;
System.out.println( countArray(N, K));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 Program to find the number # of arrays of size N whose elements # are positive integers and sum is K # Return nCr def binomialCoeff(n, k): C = [0] * (k + 1); C[0] = 1; # nC0 is 1 for i in range(1, n + 1): # Compute next row of pascal # triangle using the previous row for j in range(min(i, k), 0, -1): C[j] = C[j] + C[j - 1]; return C[k]; # Return the number of array that # can be formed of size n and # sum equals to k. def countArray(N, K): return binomialCoeff(K - 1, N - 1); # Driver Code N = 2; K = 3; print(countArray(N, K)); # This code is contributed by mits
C#
// C# Program to find the
// number of arrays of size
// N whose elements are positive
// integers and sum is K
using System;
class GFG
{
// Return nCr
static int binomialCoeff(int n,
int k)
{
int []C = new int[k + 1];
C[0] = 1; // nC0 is 1
for (int i = 1; i <= n; i++)
{
// Compute next row of
// pascal triangle using
// the previous row
for (int j = Math.Min(i, k);
j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// Return the number of
// array that can be
// formed of size n and
// sum equals to k.
static int countArray(int N,
int K)
{
return binomialCoeff(K - 1,
N - 1);
}
// Driver Code
static public void Main ()
{
int N = 2, K = 3;
Console.WriteLine(
countArray(N, K));
}
}
// This code is contributed by ajit
PHP
<?php
// PHP Program to find the
// number of arrays of size
// N whose elements are
// positive integers and
// sum is K
// Return nCr
function binomialCoeff($n, $k)
{
$C = array_fill(0, ($k + 1), 0);
$C[0] = 1; // nC0 is 1
for ($i = 1; $i <= $n; $i++)
{
// Compute next row
// of pascal triangle
// using the previous row
for ($j = min($i, $k);
$j > 0; $j--)
$C[$j] = $C[$j] +
$C[$j - 1];
}
return $C[$k];
}
// Return the number of
// array that can be
// formed of size n and
// sum equals to k.
function countArray($N, $K)
{
return binomialCoeff($K - 1,
$N - 1);
}
// Driver Code
$N = 2;
$K = 3;
echo countArray($N, $K);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript Program to find the number of arrays of
// size N whose elements are positive integers
// and sum is K
// Return nCr
function binomialCoeff(n, k)
{
var C = Array(k+1).fill(0);
C[0] = 1; // nC0 is 1
for (var i = 1; i <= n; i++) {
// Compute next row of pascal triangle using
// the previous row
for (var j = Math.min(i, k); j > 0; j--)
C[j] = C[j] + C[j - 1];
}
return C[k];
}
// Return the number of array that can be
// formed of size n and sum equals to k.
function countArray(N, K)
{
return binomialCoeff(K - 1, N - 1);
}
// Driver Code
var N = 2, K = 3;
document.write( countArray(N, K));
</script>
Producción:
2