Recuento de sumas distintas formadas por N números tomados del rango [L, R]

Dados tres números enteros N , L y R . La tarea es contar distintas sumas formadas usando N números del rango [L, R] , donde cualquier número puede tomarse infinitas veces.

Ejemplos:

Entrada: N = 2, L = 1, R = 3
Salida: 5
Explicación: Generando todas las combinaciones distintas de 2 números tomados del rango [1, 3]
{1, 1} => suma = 2
{1, 2} = > suma = 3
{1, 3} => suma = 4
{2, 2} => suma = 4
{2, 3} => suma = 5
{3, 3} => suma = 6
Por lo tanto, hay 5 ( 2, 3, 4, 5, 6) diferentes sumas posibles con 2 números tomados del rango [1, 3].

Entrada: N = 3, L = 1, R = 9
Salida: 10

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las combinaciones posibles de N números del rango [L, R] y luego contar las distintas sumas totales formadas por esas combinaciones.

Complejidad de Tiempo: O((R – L) ^N )
Espacio Auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver con algo de observación y con el uso de algunas matemáticas. Aquí los números mínimos y máximos que se pueden usar son L y R respectivamente. Entonces, la suma mínima y máxima posible que se puede formar es L*N (todos los N números son L) y R*N (todos los N números son R) respectivamente. De manera similar, también se pueden formar todas las demás sumas entre este rango. Siga los pasos a continuación para resolver el problema dado.

• Inicialice una variable, por ejemplo, minSum = L*N , para almacenar la suma mínima posible.
• Inicialice una variable, digamos maxSum = R*N , para almacenar la suma máxima posible.
• La respuesta final es el total de números en el rango [minSum, maxSum] es decir, (maxSum – minSum + 1) .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find total number of
// different sums of N numbers in
// the range [L, R]
int countDistinctSums(int N, int L, int R)
{
 
    // To store minimum possible sum with
    // N numbers with all as L
    int minSum = L * N;
 
    // To store maximum possible sum with
    // N numbers with all as R
    int maxSum = R * N;
 
    // All other numbers in between maxSum
    // and minSum can also be formed so numbers
    // in this range is the final answer
    return maxSum - minSum + 1;
}
 
// Driver Code
int main()
{
    int N = 2, L = 1, R = 3;
    cout << countDistinctSums(N, L, R);
 
    return 0;
}

// Java program for the above approach
 
import java.util.*;
 
class GFG{
 
// Function to find total number of
// different sums of N numbers in
// the range [L, R]
static int countDistinctSums(int N, int L, int R)
{
 
    // To store minimum possible sum with
    // N numbers with all as L
    int minSum = L * N;
 
    // To store maximum possible sum with
    // N numbers with all as R
    int maxSum = R * N;
 
    // All other numbers in between maxSum
    // and minSum can also be formed so numbers
    // in this range is the final answer
    return maxSum - minSum + 1;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2, L = 1, R = 3;
    System.out.print(countDistinctSums(N, L, R));
 
}
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function to find total number of
# different sums of N numbers in
# the range [L, R]
def countDistinctSums(N, L, R):
 
    # To store minimum possible sum with
    # N numbers with all as L
    minSum = L * N
 
    # To store maximum possible sum with
    # N numbers with all as R
    maxSum = R * N
 
    # All other numbers in between maxSum
    # and minSum can also be formed so numbers
    # in this range is the final answer
    return maxSum - minSum + 1
 
# Driver Code
if __name__ == "__main__":
    N = 2
    L = 1
    R = 3
    print(countDistinctSums(N, L, R))
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find total number of
// different sums of N numbers in
// the range [L, R]
static int countDistinctSums(int N, int L, int R)
{
 
    // To store minimum possible sum with
    // N numbers with all as L
    int minSum = L * N;
 
    // To store maximum possible sum with
    // N numbers with all as R
    int maxSum = R * N;
 
    // All other numbers in between maxSum
    // and minSum can also be formed so numbers
    // in this range is the final answer
    return maxSum - minSum + 1;
}
 
// Driver Code
public static void Main()
{
    int N = 2, L = 1, R = 3;
    Console.Write(countDistinctSums(N, L, R));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find total number of
        // different sums of N numbers in
        // the range [L, R]
        function countDistinctSums(N, L, R) {
 
            // To store minimum possible sum with
            // N numbers with all as L
            let minSum = L * N;
 
            // To store maximum possible sum with
            // N numbers with all as R
            let maxSum = R * N;
 
            // All other numbers in between maxSum
            // and minSum can also be formed so numbers
            // in this range is the final answer
            return maxSum - minSum + 1;
        }
 
        // Driver Code
 
        let N = 2, L = 1, R = 3;
        document.write(countDistinctSums(N, L, R));
 
// This code is contributed by Potta Lokesh
    </script>

5

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)