Dados tres enteros a , b y c . Debe seleccionar un número entero del rango [a, b] y un número entero del rango [b, c] y agregarlos. La tarea de calcular el número de formas de obtener la suma de todos los números en el rango [1, b+c].
Ejemplos:
Entrada: a = 1, b = 2, c = 2
Salida: 0, 0, 1, 1
Explicación:
Los números a obtener son [1, b+c] = [1, 4] = {1, 2, 3 , 4}
Por lo tanto, el número de formas de obtener cada uno es:
1 – no se puede obtener
2 – no se puede obtener
3 – solo una forma. seleccione {1} del rango [a, b] y {2} del rango [b, c] – 1 + 2 = 3
4 – solo de una manera. seleccione {2} del rango [a, b] y {2} del rango [b, c] – 2 + 2 = 4Entrada: a = 1, b = 3, c = 4
Salida: 0, 0, 0, 1, 2, 2, 1
Enfoque sencillo:
- Una solución simple de fuerza bruta será usar un bucle anidado donde el bucle exterior atraviesa desde i = a hasta i = b y el bucle interior desde j = b hasta j = c inclusive.
- Inicializaremos la array a de tamaño b + c + 1 con cero. Ahora en bucles, incrementaremos el índice en i+j, es decir, (a[i+j]++) .
- Simplemente imprimiremos la array al final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to calculate
// the number of ways
#include <bits/stdc++.h>
using namespace std;
void CountWays(int a, int b, int c)
{
int x = b + c + 1;
int arr[x] = { 0 };
// Initialising the array with zeros.
// You can do using memset too.
for (int i = a; i <= b; i++) {
for (int j = b; j <= c; j++) {
arr[i + j]++;
}
}
// Printing the array
for (int i = 1; i < x; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// Driver code
int main()
{
int a = 1;
int b = 2;
int c = 2;
CountWays(a, b, c);
return 0;
}
Java
// Java program to calculate
// the number of ways
class GFG{
public static void CountWays(int a, int b,
int c)
{
int x = b + c + 1;
int[] arr = new int[x];
// Initialising the array with zeros.
// You can do using memset too.
for(int i = a; i <= b; i++)
{
for(int j = b; j <= c; j++)
{
arr[i + j]++;
}
}
// Printing the array
for(int i = 1; i < x; i++)
{
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int a = 1;
int b = 2;
int c = 2;
CountWays(a, b, c);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to calculate # the number of ways def CountWays(a, b, c): x = b + c + 1; arr = [0] * x; # Initialising the array with zeros. # You can do using memset too. for i in range(a, b + 1): for j in range(b, c + 1): arr[i + j] += 1; # Printing the array for i in range(1, x): print(arr[i], end = " "); # Driver code if __name__ == '__main__': a = 1; b = 2; c = 2; CountWays(a, b, c); # This code is contributed by Rajput-Ji
C#
// C# program to calculate
// the number of ways
using System;
class GFG{
public static void CountWays(int a, int b,
int c)
{
int x = b + c + 1;
int[] arr = new int[x];
// Initialising the array with zeros.
// You can do using memset too.
for(int i = a; i <= b; i++)
{
for(int j = b; j <= c; j++)
{
arr[i + j]++;
}
}
// Printing the array
for(int i = 1; i < x; i++)
{
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main()
{
int a = 1;
int b = 2;
int c = 2;
CountWays(a, b, c);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to calculate
// the number of ways
function CountWays(a, b, c)
{
let x = b + c + 1;
let arr = new Array(x);
arr.fill(0);
// Initialising the array with zeros.
// You can do using memset too.
for (let i = a; i <= b; i++) {
for (let j = b; j <= c; j++) {
arr[i + j]++;
}
}
// Printing the array
for (let i = 1; i < x; i++) {
document.write(arr[i] + " ");
}
document.write("</br>");
}
// Driver code
let a = 1;
let b = 2;
let c = 2;
CountWays(a, b, c);
</script>
0 0 1 1
Complejidad temporal: O((ba)*(cb)), que en el peor de los casos es O(c 2 )
Espacio Auxiliar: O(x), ya que estamos usando espacio extra.
Enfoque eficiente: la idea es utilizar la lógica Prefix Sum para resolver este problema.
- Recorreremos i desde [a, b] y para cada i simplemente incrementaremos el valor del intervalo inicial arr[i + b] en 1 y disminuiremos el valor del intervalo final arr[i + c + 1] en 1.
- Ahora todo lo que tenemos que hacer es calcular la suma del prefijo de la array ( arr[i]+ = arr[i-1] ) e imprimir la array.
Veamos el enfoque con la ayuda de un ejemplo.
¿Por qué funciona esto?
Por ejemplo: a = 1, b = 2, c = 2, encontraremos solo dos valores de i
i = 1 = > arr[1+2]++; arreglo[1+2+1]–;
i = 2 = > array[2+2]++; arreglo[2+2+1]–;
array = {0, 0, 0, 1, 0, -1};
sumas de prefijos:
arr = {0, 0, 0, 1, 1, 0};
Ahora mira atentamente y date cuenta de que esta es nuestra respuesta.
Entonces, lo que hacemos en el índice particular i es arr[i+b]++ y arr[i+c+1]–;
Ahora estamos usando sumas de prefijos, por lo que todos los valores se incrementarán en 1 entre i+b e infinito (no iremos allí, pero resultará en un incremento de la suma de prefijos en 1 y tan pronto como hagamos una disminución en i+c+ 1 todos los valores entre i+c+1 e infinito disminuirán en 1.
Así que efectivamente todos los valores en el rango [i+b, i+c] se incrementan en uno, y el resto de los valores no se verán afectados.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to calculate
// the number of ways
#include <bits/stdc++.h>
using namespace std;
void CountWays(int a, int b, int c)
{
// 2 is added because sometimes
// we will decrease the
// value out of bounds.
int x = b + c + 2;
// Initialising the array with zeros.
// You can do using memset too.
int arr[x] = { 0 };
for (int i = 1; i <= b; i++) {
arr[i + b]++;
arr[i + c + 1]--;
}
// Printing the array
for (int i = 1; i < x - 1; i++) {
arr[i] += arr[i - 1];
cout << arr[i] << " ";
}
cout << endl;
}
// Driver code
int main()
{
int a = 1;
int b = 2;
int c = 2;
CountWays(a, b, c);
return 0;
}
Java
// Java program to calculate
// the number of ways
import java.util.*;
class GFG{
static void CountWays(int a, int b, int c)
{
// 2 is added because sometimes
// we will decrease the
// value out of bounds.
int x = b + c + 2;
// Initialising the array with zeros.
int arr[] = new int[x];
for(int i = 1; i <= b; i++)
{
arr[i + b]++;
arr[i + c + 1]--;
}
// Printing the array
for(int i = 1; i < x - 1; i++)
{
arr[i] += arr[i - 1];
System.out.print(arr[i] + " ");
}
System.out.println();
}
// Driver code
public static void main(String[] args)
{
int a = 1;
int b = 2;
int c = 2;
CountWays(a, b, c);
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program to calculate # the number of ways def CountWays(a, b, c): # 2 is added because sometimes # we will decrease the # value out of bounds. x = b + c + 2; # Initialising the array with zeros. arr = [0] * x; for i in range(1, b+1): arr[i + b] = arr[i + b] + 1; arr[i + c + 1] = arr[i + c + 1] -1; # Printing the array for i in range(1, x-1): arr[i] += arr[i - 1]; print(arr[i], end = " "); # Driver code if __name__ == '__main__': a = 1; b = 2; c = 2; CountWays(a, b, c); # This code is contributed by rock_cool
C#
// C# program to calculate
// the number of ways
using System;
class GFG{
static void CountWays(int a, int b, int c)
{
// 2 is added because sometimes
// we will decrease the
// value out of bounds.
int x = b + c + 2;
// Initialising the array with zeros.
int []arr = new int[x];
for(int i = 1; i <= b; i++)
{
arr[i + b]++;
arr[i + c + 1]--;
}
// Printing the array
for(int i = 1; i < x - 1; i++)
{
arr[i] += arr[i - 1];
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
// Driver code
public static void Main()
{
int a = 1;
int b = 2;
int c = 2;
CountWays(a, b, c);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program to calculate
// the number of ways
function CountWays(a, b, c)
{
// 2 is added because sometimes
// we will decrease the
// value out of bounds.
let x = b + c + 2;
// Initialising the array with zeros.
// You can do using memset too.
let arr = new Array(x);
arr.fill(0);
for(let i = 1; i <= b; i++)
{
arr[i + b]++;
arr[i + c + 1]--;
}
// Printing the array
for(let i = 1; i < x - 1; i++)
{
arr[i] += arr[i - 1];
document.write(arr[i] + " ");
}
document.write("</br>");
}
// Driver code
let a = 1;
let b = 2;
let c = 2;
CountWays(a, b, c);
// This code is contributed by rameshtravel07
</script>
0 0 1 1
Complejidad de tiempo: O(b+c), ya que estamos usando loop para atravesar tiempos b+c.
Espacio auxiliar : O(b+c), ya que estamos usando espacio extra.
Publicación traducida automáticamente
Artículo escrito por codebuddy_1903 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA