Dado un número N y dos arrays arr1[] y arr2[] de longitud 4. La array arr1[] denota la denominación de 1, 5, 10 y 20 y arr2[] denota el recuento de denominaciones de 1, 5, 10 , y 20 respectivamente. La tarea es encontrar el número de formas en que podemos sumarlas hasta un total de N con un número limitado de denominaciones.
Ejemplos:
Entrada: arr1[] = {1, 5, 10, 20}, arr2[] = {6, 4, 3, 5}, N = 123
Salida: 5
Explicación:
Hay 5 formas de sumar hasta 123 con el dado denominación de las monedas.
Entrada: arr1[] = {1, 5, 10, 20}, arr2[] = {1, 3, 2, 1}, N = 50
Salida: 1
Explicación:
Solo hay 1 forma de sumar hasta 50 con el denominación dada de las monedas.
Enfoque ingenuo: deje que el recuento de denominaciones esté representado por A, B, C y D. El enfoque ingenuo es ejecutar bucles anidados. Cada lazo se referirá al número de monedas de cada denominación. Encuentre el número de monedas de cada denominación requeridas para formar N mediante la ecuación:
(a * 1) + (b * 5) + (c * 10) + (d * 20)) == N
donde 0 <= a <= A, 0 &<= b <= B, 0 <= c < = C, 0 <= d <= D y N es la cantidad total.
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(1)
Mejor enfoque: podemos optimizar el enfoque ingenuo anterior agregando algunos límites adicionales a los bucles que reducirán algunos cálculos. Al observar, podemos reducir fácilmente la complejidad al descartar un bucle al eliminar la moneda con la denominación 1 de N y verificar si la siguiente desigualdad es cierta o no:
(N – A) <= (segunda * 5 + c * 10 + re * 20) <= norte
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 to find the number of
// ways to sum up a total of N
// from limited denominations
int calculateWays(int arr1[], int arr2[],
int N)
{
// Store the count of denominations
int A = arr2[0], B = arr2[1];
int C = arr2[2], D = arr2[3];
// Stores the final result
int ans = 0;
// As one of the denominations is
// rupee 1, so we can reduce the
// computation by checking the
// equality for N-(A*1) = N-A
for (int b = 0;
b <= B && b * 5 <= (N); b++)
for (int c = 0;
c <= C
&& b * 5 + c * 10 <= (N);
c++)
for (int d = 0;
d <= D
&& b * 5 + c * 10 + d * 20 <= (N);
d++)
if ((b * 5) + (c * 10)
+ (d * 20)
>= (N - A))
// Increment the count
// for number of ways
ans++;
return ans;
}
// Driver Code
int main()
{
// Given Denominations
int N = 123;
int arr1[] = { 1, 5, 10, 20 };
int arr2[] = { 6, 4, 3, 5 };
// Function Call
cout << calculateWays(arr1, arr2, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
static int calculateWays(int arr1[], int arr2[],
int N)
{
// Store the count of denominations
int A = arr2[0], B = arr2[1];
int C = arr2[2], D = arr2[3];
// Stores the final result
int ans = 0;
// As one of the denominations is
// rupee 1, so we can reduce the
// computation by checking the
// equality for N-(A*1) = N-A
for(int b = 0;
b <= B && b * 5 <= (N); b++)
for(int c = 0;
c <= C && b * 5 + c * 10 <= (N);
c++)
for(int d = 0;
d <= D &&
b * 5 + c * 10 + d * 20 <= (N);
d++)
if ((b * 5) + (c * 10) +
(d * 20) >= (N - A))
// Increment the count
// for number of ways
ans++;
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given denominations
int N = 123;
int arr1[] = { 1, 5, 10, 20 };
int arr2[] = { 6, 4, 3, 5 };
// Function call
System.out.print(calculateWays(arr1, arr2, N));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for the above approach # Function to find the number of # ways to sum up a total of N # from limited denominations def calculateWays(arr1, arr2, N): # Store the count of denominations A = arr2[0] B = arr2[1] C = arr2[2] D = arr2[3] # Stores the final result ans, b, c, d = 0, 0, 0, 0 # As one of the denominations is # rupee 1, so we can reduce the # computation by checking the # equality for N-(A*1) = N-A while b <= B and b * 5 <= (N): c = 0 while (c <= C and b * 5 + c * 10 <= (N)): d = 0 while (d <= D and b * 5 + c * 10 + d * 20 <= (N)): if ((b * 5) + (c * 10) + (d * 20) >= (N - A)): # Increment the count # for number of ways ans += 1 d += 1 c += 1 b += 1 return ans # Driver Code if __name__ == '__main__': # Given Denominations N = 123 arr1 = [ 1, 5, 10, 20 ] arr2 = [ 6, 4, 3, 5 ] # Function Call print(calculateWays(arr1, arr2, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
static int calculateWays(int []arr1, int []arr2,
int N)
{
// Store the count of denominations
int A = arr2[0], B = arr2[1];
int C = arr2[2], D = arr2[3];
// Stores the readonly result
int ans = 0;
// As one of the denominations is
// rupee 1, so we can reduce the
// computation by checking the
// equality for N-(A*1) = N-A
for(int b = 0;
b <= B && b * 5 <= (N); b++)
for(int c = 0;
c <= C && b * 5 + c * 10 <= (N);
c++)
for(int d = 0;
d <= D &&
b * 5 + c * 10 + d * 20 <= (N);
d++)
if ((b * 5) + (c * 10) +
(d * 20) >= (N - A))
// Increment the count
// for number of ways
ans++;
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given denominations
int N = 123;
int []arr1 = { 1, 5, 10, 20 };
int []arr2 = { 6, 4, 3, 5 };
// Function call
Console.Write(calculateWays(arr1, arr2, N));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
function calculateWays(arr1, arr2,
N)
{
// Store the count of denominations
let A = arr2[0], B = arr2[1];
let C = arr2[2], D = arr2[3];
// Stores the final result
let ans = 0;
// As one of the denominations is
// rupee 1, so we can reduce the
// computation by checking the
// equality for N-(A*1) = N-A
for(let b = 0;
b <= B && b * 5 <= (N); b++)
for(let c = 0;
c <= C && b * 5 + c * 10 <= (N);
c++)
for(let d = 0;
d <= D &&
b * 5 + c * 10 + d * 20 <= (N);
d++)
if ((b * 5) + (c * 10) +
(d * 20) >= (N - A))
// Increment the count
// for number of ways
ans++;
return ans;
}
// Driver Code
// Given denominations
let N = 123;
let arr1 = [ 1, 5, 10, 20 ];
let arr2 = [ 6, 4, 3, 5 ];
// Function call
document.write(calculateWays(arr1, arr2, N));
</script>
Producción:
5
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Deje que el conteo de denominaciones esté representado por A, B, C y D. El enfoque eficiente para resolver el problema anterior es contar el número posible de denominaciones formadas usando C y D. Luego encontraremos el valor restante con denominaciones de A y B. A continuación se muestran los pasos:
- Inicialice la arrayways [] para almacenar la suma precalculada de las denominaciones de A y B.
- Iterar dos bucles anidados para almacenar la combinación de valores formada por las denominaciones de A y B enways [] .
- Iterar dos bucles anidados para encontrar todas las combinaciones de valores formadas por las denominaciones de C y D y sumar todas las combinaciones posibles del valor N – (C*10 + D*20) , que es equivalente a (A * 1) + ( B * 5) .
- La suma de todos los valores en el paso anterior es el resultado requerido.
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;
int ways[1010];
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
int calculateWays(int arr1[], int arr2[],
int N)
{
// Store the count of denominations
int A = arr2[0], B = arr2[1];
int C = arr2[2], D = arr2[3];
// Stores the final result
int ans = 0;
// L1 : Incrementing the values
// with indices with denomination
// (a * 1 + b * 5)
// This will give the number of coins
// for all combinations of coins
// with value 1 and 5
for (int b = 0;
b <= B && b * 5 <= N; b++) {
for (int a = 0;
a <= A
&& a * 1 + b * 5 <= N;
a++) {
ways[a + b * 5]++;
}
}
// L2 will sum the values of those
// indices of ways[] which is equal
// to (N - (c * 10 + d * 20))
for (int c = 0;
c <= C && c * 10 <= (N); c++) {
for (int d = 0;
d <= D
&& c * 10 + d * 20 <= (N);
d++) {
ans += ways[N - c * 10 - d * 20];
}
}
// Return the final count
return ans;
}
// Driver Code
int main()
{
// Given Denominations
int N = 123;
int arr1[] = { 1, 5, 10, 20 };
int arr2[] = { 6, 4, 3, 5 };
// Function Call
cout << calculateWays(arr1, arr2, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int []ways = new int[1010];
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
static int calculateWays(int arr1[], int arr2[],
int N)
{
// Store the count of denominations
int A = arr2[0], B = arr2[1];
int C = arr2[2], D = arr2[3];
// Stores the final result
int ans = 0;
// L1 : Incrementing the values
// with indices with denomination
// (a * 1 + b * 5)
// This will give the number of coins
// for all combinations of coins
// with value 1 and 5
for(int b = 0;
b <= B && b * 5 <= N; b++)
{
for(int a = 0;
a <= A && a * 1 + b * 5 <= N;
a++)
{
ways[a + b * 5]++;
}
}
// L2 will sum the values of those
// indices of ways[] which is equal
// to (N - (c * 10 + d * 20))
for(int c = 0;
c <= C && c * 10 <= (N); c++)
{
for(int d = 0;
d <= D && c * 10 + d * 20 <= (N);
d++)
{
ans += ways[N - c * 10 - d * 20];
}
}
// Return the final count
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given denominations
int N = 123;
int arr1[] = { 1, 5, 10, 20 };
int arr2[] = { 6, 4, 3, 5 };
// Function call
System.out.print(calculateWays(arr1, arr2, N));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for # the above approach ways = [0 for i in range(1010)]; # Function to find the number of # ways to sum up a total of N # from limited denominations def calculateWays(arr1, arr2, N): # Store the count of denominations A = arr2[0]; B = arr2[1]; C = arr2[2]; D = arr2[3]; # Stores the final result ans = 0; # L1 : Incrementing the values # with indices with denomination # (a * 1 + b * 5) # This will give the number of coins # for all combinations of coins # with value 1 and 5 for b in range(0, B + 1): if(b * 5 > N): break; for a in range(0, A + 1): if(a + b * 5 > N): break; ways[a + b * 5] += 5; # L2 will sum the values of those # indices of ways which is equal # to (N - (c * 10 + d * 20)) for c in range(0, C): if(c * 10 > N): break; for d in range(0, D): if(c * 10 + d * 20 > N): break; ans += ways[N - c * 10 - d * 20]; # Return the final count return ans; # Driver Code if __name__ == '__main__': # Given denominations N = 123; arr1 = [1, 5, 10, 20]; arr2 = [6, 4, 3, 5]; # Function call print(calculateWays(arr1, arr2, N)); # This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
class GFG{
static int []ways = new int[1010];
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
static int calculateWays(int []arr1, int []arr2,
int N)
{
// Store the count of denominations
int A = arr2[0], B = arr2[1];
int C = arr2[2], D = arr2[3];
// Stores the readonly result
int ans = 0;
// L1 : Incrementing the values
// with indices with denomination
// (a * 1 + b * 5)
// This will give the number of coins
// for all combinations of coins
// with value 1 and 5
for(int b = 0;
b <= B && b * 5 <= N; b++)
{
for(int a = 0;
a <= A && a * 1 + b * 5 <= N;
a++)
{
ways[a + b * 5]++;
}
}
// L2 will sum the values of those
// indices of ways[] which is equal
// to (N - (c * 10 + d * 20))
for(int c = 0;
c <= C && c * 10 <= (N); c++)
{
for(int d = 0;
d <= D && c * 10 + d * 20 <= (N);
d++)
{
ans += ways[N - c * 10 - d * 20];
}
}
// Return the final count
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given denominations
int N = 123;
int []arr1 = { 1, 5, 10, 20 };
int []arr2 = { 6, 4, 3, 5 };
// Function call
Console.Write(calculateWays(arr1, arr2, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
var ways = Array(1010).fill(0);
// Function to find the number of
// ways to sum up a total of N
// from limited denominations
function calculateWays(arr1, arr2, N)
{
// Store the count of denominations
var A = arr2[0], B = arr2[1];
var C = arr2[2], D = arr2[3];
// Stores the final result
var ans = 0;
// L1 : Incrementing the values
// with indices with denomination
// (a * 1 + b * 5)
// This will give the number of coins
// for all combinations of coins
// with value 1 and 5
for (var b = 0;
b <= B && b * 5 <= N; b++) {
for (var a = 0;
a <= A
&& a * 1 + b * 5 <= N;
a++) {
ways[a + b * 5]++;
}
}
// L2 will sum the values of those
// indices of ways[] which is equal
// to (N - (c * 10 + d * 20))
for (var c = 0;
c <= C && c * 10 <= (N); c++) {
for (var d = 0;
d <= D
&& c * 10 + d * 20 <= (N);
d++) {
ans += ways[N - c * 10 - d * 20];
}
}
// Return the final count
return ans;
}
// Driver Code
// Given Denominations
var N = 123;
var arr1 = [1, 5, 10, 20];
var arr2 = [6, 4, 3, 5];
// Function Call
document.write( calculateWays(arr1, arr2, N));
</script>
Producción:
5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por asknishant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA