Recuento de arrays no decrecientes de longitud N formadas con valores en el rango L a R

Dados los números enteros N , L y R , la tarea es contar el número de arrays no decrecientes de longitud N formadas con valores en el rango [L, R] con repetición permitida.
Ejemplos: 
 

Entrada: N = 4, L = 4, R = 6 
Salida:
Todas las arrays posibles son {4, 4, 4, 6}, {4, 4, 5, 6}, {4, 5, 5, 6}, {4, 5, 6, 6} y {4, 6, 6, 6}.
Entrada: N = 2, L = 5, R = 2 
Salida:
No existen combinaciones como L > R. 
 

Acercarse: 
 

  • Dado que se sabe que el número mínimo es L y el número máximo es R en la array.
  • Si los índices restantes (N-2) se llenan con L , se obtiene la suma mínima posible y si los índices restantes (N-2) se llenan con R , se obtiene la suma máxima posible .
  • Se puede concluir que existe una combinación de números que da como resultado una suma entre la mínima y la máxima suma posible.
  • Por lo tanto, el número total diferente de sumas se puede calcular mediante: 
    [(N – 2) * R – (N – 2) * L] + 1 = (N – 2) * (R – L) + 1 
     

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

C++

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of different arrays
int countSum(int N, int L, int R)
{
 
    // No such combination exists
    if (L > R) {
        return 0;
    }
 
    // Arrays formed with single elements
    if (N == 1) {
        return R - L + 1;
    }
 
    if (N > 1) {
        return (N - 2) * (R - L) + 1;
    }
}
 
// Driver code
int main()
{
    int N = 4, L = 4, R = 6;
 
    cout << countSum(N, L, R);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Function to return the count
// of different arrays
static int countSum(int N, int L, int R)
{
 
    // No such combination exists
    if (L > R)
    {
        return 0;
    }
 
    // Arrays formed with single elements
    if (N == 1)
    {
        return R - L + 1;
    }
 
    if (N > 1)
    {
        return (N - 2) * (R - L) + 1;
    }
    return 0;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4, L = 4, R = 6;
 
    System.out.print(countSum(N, L, R));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
 
# Function to return the count
# of different arrays
def countSum(N, L, R):
 
    # No such combination exists
    if (L > R):
        return 0;
 
    # Arrays formed with single elements
    if (N == 1):
        return R - L + 1;
    if (N > 1):
        return (N - 2) * (R - L) + 1;
     
    return 0;
 
# Driver code
if __name__ == '__main__':
    N, L, R = 4, 4, 6;
 
    print(countSum(N, L, R));
 
# This code is contributed by 29AjayKumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count
// of different arrays
static int countSum(int N, int L, int R)
{
 
    // No such combination exists
    if (L > R)
    {
        return 0;
    }
 
    // Arrays formed with single elements
    if (N == 1)
    {
        return R - L + 1;
    }
 
    if (N > 1)
    {
        return (N - 2) * (R - L) + 1;
    }
    return 0;
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 4, L = 4, R = 6;
 
    Console.Write(countSum(N, L, R));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the count
// of different arrays
function countSum(N, L, R)
{
 
    // No such combination exists
    if (L > R) {
        return 0;
    }
 
    // Arrays formed with single elements
    if (N == 1) {
        return R - L + 1;
    }
 
    if (N > 1) {
        return (N - 2) * (R - L) + 1;
    }
}
 
// Driver code
var N = 4, L = 4, R = 6;
document.write( countSum(N, L, R));
 
// This code is contributed by noob2000.
</script>
Producción: 

5

 

Complejidad de tiempo: O(1)
 

Publicación traducida automáticamente

Artículo escrito por souradeep 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 *