Dado un número n (número de variables) y val (suma de las variables), averigüe cuántas soluciones integrales no negativas son posibles.
Ejemplos:
Input : n = 5, val = 1 Output : 5 Explanation: x1 + x2 + x3 + x4 + x5 = 1 Number of possible solution are : (0 0 0 0 1), (0 0 0 1 0), (0 0 1 0 0), (0 1 0 0 0), (1 0 0 0 0) Total number of possible solutions are 5 Input : n = 5, val = 4 Output : 70 Explanation: x1 + x2 + x3 + x4 + x5 = 4 Number of possible solution are: (1 1 1 1 0), (1 0 1 1 1), (0 1 1 1 1), (2 1 0 0 1), (2 2 0 0 0)........ so on...... Total numbers of possible solutions are 70
Preguntado en: Entrevista de Microsoft
1. Realice una llamada de función recursiva a countSolutions(int n, int val)
2. Llame a esta función de solución countSolutions(n-1, val-i) hasta que n = 1 y val >=0 y luego devuelva 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the numbers
// of non negative integral solutions
#include<iostream>
using namespace std;
// return number of non negative
// integral solutions
int countSolutions(int n, int val)
{
// initialize total = 0
int total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >=0)
return 1;
// iterate the loop till equal the val
for (int i = 0; i <= val; i++){
// total solution of equations
// and again call the recursive
// function Solutions(variable,value)
total += countSolutions(n-1, val-i);
}
// return the total no possible solution
return total;
}
// driver code
int main(){
int n = 5;
int val = 20;
cout<<countSolutions(n, val);
}
//This code is contributed by Smitha Dinesh Semwal
Java
// Java program to find the numbers
// of non negative integral solutions
class GFG {
// return number of non negative
// integral solutions
static int countSolutions(int n, int val) {
// initialize total = 0
int total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >= 0)
return 1;
// iterate the loop till equal the val
for (int i = 0; i <= val; i++) {
// total solution of equations
// and again call the recursive
// function Solutions(variable, value)
total += countSolutions(n - 1, val - i);
}
// return the total no possible solution
return total;
}
// Driver code
public static void main(String[] args) {
int n = 5;
int val = 20;
System.out.print(countSolutions(n, val));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find the numbers # of non negative integral solutions # return number of non negative # integral solutions def countSolutions(n, val): # initialize total = 0 total = 0 # Base Case if n = 1 and val >= 0 # then it should return 1 if n == 1 and val >=0: return 1 # iterate the loop till equal the val for i in range(val+1): # total solution of equations # and again call the recursive # function Solutions(variable,value) total += countSolutions(n-1, val-i) # return the total no possible solution return total # driver code n = 5 val = 20 print(countSolutions(n, val))
C#
// C# program to find the numbers
// of non negative integral solutions
using System;
class GFG {
// return number of non negative
// integral solutions
static int countSolutions(int n, int val) {
// initialize total = 0
int total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >= 0)
return 1;
// iterate the loop till equal the val
for (int i = 0; i <= val; i++) {
// total solution of equations
// and again call the recursive
// function Solutions(variable, value)
total += countSolutions(n - 1, val - i);
}
// return the total no possible solution
return total;
}
// Driver code
public static void Main()
{
int n = 5;
int val = 20;
Console.WriteLine(countSolutions(n, val));
}
}
// This code is contributed by Anant vt_m.
PHP
<?php
// PHP program to find the numbers
// of non negative integral solutions
// return number of non negative
// integral solutions
function countSolutions($n, $val)
{
// initialize total = 0
$total = 0;
// Base Case if n = 1 and
// val >= 0 then it should
// return 1
if ($n == 1 && $val >=0)
return 1;
// iterate the loop
// till equal the val
for ($i = 0; $i <= $val; $i++)
{
// total solution of equations
// and again call the recursive
// function Solutions(variable,value)
$total += countSolutions($n - 1,
$val - $i);
}
// return the total
// no possible solution
return $total;
}
// Driver Code
$n = 5;
$val = 20;
echo countSolutions($n, $val);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// JavaScript program to find the numbers
// of non negative integral solutions
// return number of non negative
// integral solutions
function countSolutions(n, val) {
// initialize total = 0
let total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >= 0)
return 1;
// iterate the loop till equal the val
for (let i = 0; i <= val; i++) {
// total solution of equations
// and again call the recursive
// function Solutions(variable, value)
total += countSolutions(n - 1, val - i);
}
// return the total no possible solution
return total;
}
// Driver code
let n = 5;
let val = 20;
document.write(countSolutions(n, val));
</script>
Producción :
10626
Enfoque de programación dinámica:
(Usando Memoización)
C++
// CPP program to find the numbers
// of non negative integral solutions
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
// return number of non negative
// integral solutions
int countSolutions(int n, int val)
{
// initialize total = 0
int total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >=0) {
return 1;
}
// If a value already present in dp,
// return it
if(dp[n][val] != -1) {
return dp[n][val];
}
// iterate the loop till equal the val
for (int i = 0; i <= val; i++){
// total solution of equations
// and again call the recursive
// function Solutions(variable,value)
total += countSolutions(n-1, val-i);
}
// Store the value in dp
dp[n][val] = total;
// Return dp
return dp[n][val];
}
// driver code
int main(){
int n = 5;
int val = 20;
memset(dp, -1, sizeof(dp));
cout << countSolutions(n, val);
}
Java
// Java program to find the numbers
// of non negative integral solutions
import java.util.*;
public class GFG
{
static int dp[][] = new int[1001][1001];
// return number of non negative
// integral solutions
static int countSolutions(int n, int val)
{
// initialize total = 0
int total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >=0) {
return 1;
}
// If a value already present in dp,
// return it
if(dp[n][val] != -1) {
return dp[n][val];
}
// iterate the loop till equal the val
for (int i = 0; i <= val; i++){
// total solution of equations
// and again call the recursive
// function Solutions(variable,value)
total += countSolutions(n-1, val-i);
}
// Store the value in dp
dp[n][val] = total;
// Return dp
return dp[n][val];
}
// driver code
public static void main(String args[]){
int n = 5;
int val = 20;
for(int i = 0; i < 1001; i++) {
for(int j = 0; j < 1001; j++) {
dp[i][j]=-1;
}
}
System.out.println(countSolutions(n, val));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python3 program to find the numbers # of non negative integral solutions # Taking the matrix as globally dp = [[-1 for i in range(1001)] for j in range(1001)] # Return number of non negative # integral solutions def countSolutions(n, val): # Initialize total = 0 total = 0 # Base Case if n = 1 and val >= 0 # then it should return 1 if n == 1 and val >= 0: return 1 # If a value is already present # in dp if (dp[n][val] != -1): return dp[n][val] # Iterate the loop till equal the val for i in range(val + 1): # total solution of equations # and again call the recursive # function Solutions(variable,value) total += countSolutions(n - 1, val - i) # Return the total no possible solution dp[n][val] = total return dp[n][val] # Driver code n = 5 val = 20 print(countSolutions(n, val)) # This code is contributed by Samim Hossain Mondal.
C#
// C# program to find the numbers
// of non negative integral solutions
using System;
class GFG
{
static int [,]dp = new int[1001, 1001];
// return number of non negative
// integral solutions
static int countSolutions(int n, int val)
{
// initialize total = 0
int total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >=0) {
return 1;
}
// If a value already present in dp,
// return it
if(dp[n, val] != -1) {
return dp[n, val];
}
// iterate the loop till equal the val
for (int i = 0; i <= val; i++){
// total solution of equations
// and again call the recursive
// function Solutions(variable,value)
total += countSolutions(n-1, val-i);
}
// Store the value in dp
dp[n, val] = total;
// Return dp
return dp[n, val];
}
// driver code
public static void Main(){
int n = 5;
int val = 20;
for(int i = 0; i < 1001; i++) {
for(int j = 0; j < 1001; j++) {
dp[i, j] = -1;
}
}
Console.Write(countSolutions(n, val));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to find the numbers
// of non negative integral solutions
var dp = new Array(1001);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(1001);
}
// return number of non negative
// integral solutions
function countSolutions(n, val) {
// initialize total = 0
let total = 0;
// Base Case if n = 1 and val >= 0
// then it should return 1
if (n == 1 && val >= 0)
return 1;
// if a value is already
// present in dp
if(dp[n][val] != -1)
return dp[n][val];
// iterate the loop till equal the val
for (let i = 0; i <= val; i++) {
// total solution of equations
// and again call the recursive
// function Solutions(variable, value)
total += countSolutions(n - 1, val - i);
}
// return the total no possible solution
return dp[n][val] = total;
}
// Driver code
let n = 5;
let val = 20;
for(let i = 0; i < 1001; i++) {
for(let j = 0; j < 1001; j++) {
dp[i][j] = -1;
}
}
document.write(countSolutions(n, val));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
10626
Complejidad temporal: O(n * val)
Espacio Auxiliar: O(n * val)
Publicación traducida automáticamente
Artículo escrito por shrikanth13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA