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: 5
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: 0
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)