Cuente las posibles divisiones de la suma N en K enteros de modo que el mínimo sea al menos P

Posted on by Rudeus Greyrat

Dados tres enteros N , P y K , la tarea es encontrar el número total de formas de dividir N en K enteros que tengan una suma N donde cada entero sea ≥ P .

Ejemplos:

Entrada: K = 3, N = 8, P = 2
Salida: 6
Explicación:
Seis soluciones posibles son: {2, 2, 4}, {2, 3, 3}, {2, 4, 2}, {3, 2, 3}, {3, 3, 2}, {4, 2, 2}
Cada uno de los números anteriores en todas las combinaciones son ≥ P(= 2) y la suma de todas las combinaciones es N(=8).

Entrada: K = 2, N = 7, P = 2
Salida: 4
Explicación: Las
cuatro posibles soluciones son: {4, 3}, {3, 4}, {5, 2}, {2, 5}
Cada una de las anteriores los enteros en todas las combinaciones son ≥ P(= 2) y la suma de todas las combinaciones es N(= 7).

Enfoque ingenuo: el enfoque más simple es probar todas las combinaciones posibles de K enteros que tienen una suma N y verificar si cumplen o no las condiciones anteriores. Hay K posiciones y en cada posición se pueden colocar N enteros. Por lo tanto, el número total de combinaciones a verificar es N K . 

Complejidad temporal: O(N K )
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el enfoque discutido en este artículo y las condiciones dadas anteriormente se pueden escribir en términos de una ecuación lineal:

Encontrar el número de soluciones para la ecuación X 1 + X 2 + X 3 + … + X K = N donde X i ≥ P.

Suponga que X yo ‘ = X yo – PAG .
Por lo tanto, la ecuación se reduce a:
 X 1 ‘ + X 2 ‘ + X 3 ‘ + … + X K ‘ = N – K*P

Según las ecuaciones anteriores, el problema dado se reduce a encontrar el número total de formas de dividir N – K * P en K enteros . Escriba el número total de formas encontradas arriba como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that finds the value of
// the Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n + 1][k + 1];
    int i, j;
 
    // Stores the value of Binomial
    // Coefficient in bottom up manner
    for (i = 0; i <= n; i++) {
 
        for (j = 0; j <= min(i, k); j++) {
 
            // Base Case
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Find the value using
            // previously stored values
            else
                C[i][j] = C[i - 1][j - 1]
                          + C[i - 1][j];
        }
    }
 
    // Return the value of C(N, K)
    return C[n][k];
}
 
// Function that count the number of
// ways to divide N into K integers
// >= P such that their sum is N
int waysToSplitN(int k, int n, int P)
{
    // Update the value of N
    int new_N = n - k * P;
 
    // Find the binomial coefficient
    // recursively
    return binomialCoeff(new_N + k - 1,
                         new_N);
}
 
// Driver Code
int main()
{
    // Given K, N, and P
    int K = 3, N = 8, P = 2;
 
    cout << waysToSplitN(K, N, P);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function that finds the value of
// the Binomial Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
  int [][]C = new int[n + 1][k + 1];
  int i, j;
 
  // Stores the value of Binomial
  // Coefficient in bottom up manner
  for (i = 0; i <= n; i++)
  {
    for (j = 0; j <= Math.min(i, k); j++)
    {
      // Base Case
      if (j == 0 || j == i)
        C[i][j] = 1;
 
      // Find the value using
      // previously stored values
      else
        C[i][j] = C[i - 1][j - 1] +
                  C[i - 1][j];
    }
  }
 
  // Return the value of C(N, K)
  return C[n][k];
}
 
// Function that count the number of
// ways to divide N into K integers
// >= P such that their sum is N
static int waysToSplitN(int k,
                        int n, int P)
{
  // Update the value of N
  int new_N = n - k * P;
 
  // Find the binomial coefficient
  // recursively
  return binomialCoeff(new_N + k - 1,
                       new_N);
}
 
// Driver Code
public static void main(String[] args)
{
  // Given K, N, and P
  int K = 3, N = 8, P = 2;
 
  System.out.print(waysToSplitN(K, N, P));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function that finds the value of
# the Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
 
    C = [[0 for x in range(k + 1)]
            for y in range(n + 1)]
 
    # Stores the value of Binomial
    # Coefficient in bottom up manner
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
 
            # Base Case
            if(j == 0 or j == i):
                C[i][j] = 1
                 
            # Find the value using
            # previously stored values
            else:
                C[i][j] = (C[i - 1][j - 1] +
                           C[i - 1][j])
 
    # Return the value of C(N, K)
    return C[n][k]
 
# Function that count the number of
# ways to divide N into K integers
# >= P such that their sum is N
def waysToSplitN(k, n, P):
 
    # Update the value of N
    new_N = n - k * P
 
    # Find the binomial coefficient
    # recursively
    return binomialCoeff(new_N + k - 1,
                         new_N)
 
# Driver Code
 
# Given K, N, and P
K = 3
N = 8
P = 2
 
print(waysToSplitN(K, N, P))
 
# This code is contributed by Shivam Singh

C#

// C# program for the above approach
using System;
 
class GFG{
  
// Function that finds the value of
// the Binomial Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
    int [,] C = new int[n + 1, k + 1];
    int i, j;
     
    // Stores the value of Binomial
    // Coefficient in bottom up manner
    for(i = 0; i <= n; i++)
    {
        for(j = 0; j <= Math.Min(i, k); j++)
        {
             
            // Base Case
            if (j == 0 || j == i)
                C[i, j] = 1;
             
            // Find the value using
            // previously stored values
            else
                C[i, j] = C[i - 1, j - 1] +
                          C[i - 1, j];
        }
    }
     
    // Return the value of C(N, K)
    return C[n, k];
}
  
// Function that count the number of
// ways to divide N into K integers
// >= P such that their sum is N
static int waysToSplitN(int k, int n,
                        int P)
{
     
    // Update the value of N
    int new_N = n - k * P;
     
    // Find the binomial coefficient
    // recursively
    return binomialCoeff(new_N + k - 1,
                         new_N);
}
  
// Driver Code
public static void Main()
{
     
    // Given K, N, and P
    int K = 3, N = 8, P = 2;
     
    Console.Write(waysToSplitN(K, N, P));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function that finds the value of
// the Binomial Coefficient C(n, k)
function binomialCoeff(n, k)
{
      let C = new Array(n + 1);
   
    // Loop to create 2D array using 1D array
    for (let i = 0; i < C.length; i++) {
        C[i] = new Array(2);
    }
     
  let i, j;
  
  // Stores the value of Binomial
  // Coefficient in bottom up manner
  for (i = 0; i <= n; i++)
  {
    for (j = 0; j <= Math.min(i, k); j++)
    {
      // Base Case
      if (j == 0 || j == i)
        C[i][j] = 1;
  
      // Find the value using
      // previously stored values
      else
        C[i][j] = C[i - 1][j - 1] +
                  C[i - 1][j];
    }
  }
  
  // Return the value of C(N, K)
  return C[n][k];
}
  
// Function that count the number of
// ways to divide N into K integers
// >= P such that their sum is N
function waysToSplitN(k, n, P)
{
  // Update the value of N
  let new_N = n - k * P;
  
  // Find the binomial coefficient
  // recursively
  return binomialCoeff(new_N + k - 1,
                       new_N);
}
 
// Driver Code
 
     // Given K, N, and P
  let K = 3, N = 8, P = 2;
  
  document.write(waysToSplitN(K, N, P));
     
</script>
Producción: 

6

 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )

Publicación traducida automáticamente

Artículo escrito por a_kash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *