Dados dos números N y M , la tarea es encontrar el número de arrays ordenadas que se pueden formar de tamaño M usando los primeros N números naturales , si cada número se puede tomar cualquier número de veces.
Ejemplos:
Entrada: N = 4, M = 2
Salida: 10
Explicación: Todas estas arrays posibles son {1, 1}, {1, 2}, {1, 2}, {1, 4}, {2, 2}, { 2, 3}, {2, 4}, {3, 3}, {3, 4}, {4, 4}.Entrada: N = 2, M = 4
Salida: 5
Explicación: Todas estas arrays posibles son {1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 2}, { 1, 2, 2, 2}, {2, 2, 2, 2}.
Enfoque ingenuo: hay dos opciones para cada número que se puede tomar o dejar. Además, un número se puede tomar varias veces.
- Los elementos que se toman varias veces deben ser consecutivos en la array , ya que la array debe estar ordenada.
- Si se deja un elemento y se ha movido a otro elemento, ese elemento no se puede volver a tomar.
La rama izquierda indica que se tomó el elemento y la rama derecha indica que el elemento se dejó y el puntero se movió al siguiente elemento.
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
// M-length sorted arrays possible
// using numbers from the range [1, N]
int countSortedArrays(int start, int m,
int size, int n)
{
// If size becomes equal to m,
// that means an array is found
if (size == m)
return 1;
if (start > n)
return 0;
int notTaken = 0, taken = 0;
// Include current element, increase
// size by 1 and remain on the same
// element as it can be included again
taken = countSortedArrays(start, m,
size + 1, n);
// Exclude current element
notTaken = countSortedArrays(start + 1,
m, size, n);
// Return the sum obtained
// in both the cases
return taken + notTaken;
}
// Driver Code
int main()
{
// Given Input
int n = 2, m = 3;
// Function Call
cout << countSortedArrays(1, m, 0, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(int start, int m,
int size, int n)
{
// If size becomes equal to m,
// that means an array is found
if (size == m)
return 1;
if (start > n)
return 0;
int notTaken = 0, taken = 0;
// Include current element, increase
// size by 1 and remain on the same
// element as it can be included again
taken = countSortedArrays(start, m,
size + 1, n);
// Exclude current element
notTaken = countSortedArrays(start + 1,
m, size, n);
// Return the sum obtained
// in both the cases
return taken + notTaken;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int n = 2, m = 3;
// Function Call
System.out.println(countSortedArrays(1, m, 0, n));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find the number of # M-length sorted arrays possible # using numbers from the range [1, N] def countSortedArrays(start, m, size, n): # If size becomes equal to m, # that means an array is found if (size == m): return 1 if (start > n): return 0 notTaken, taken = 0, 0 # Include current element, increase # size by 1 and remain on the same # element as it can be included again taken = countSortedArrays(start, m, size + 1, n) # Exclude current element notTaken = countSortedArrays(start + 1, m, size, n) # Return the sum obtained # in both the cases return taken + notTaken # Driver Code if __name__ == '__main__': # Given Input n, m = 2, 3 # Function Call print (countSortedArrays(1, m, 0, 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
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(int start, int m,
int size, int n)
{
// If size becomes equal to m,
// that means an array is found
if (size == m)
return 1;
if (start > n)
return 0;
int notTaken = 0, taken = 0;
// Include current element, increase
// size by 1 and remain on the same
// element as it can be included again
taken = countSortedArrays(start, m,
size + 1, n);
// Exclude current element
notTaken = countSortedArrays(start + 1,
m, size, n);
// Return the sum obtained
// in both the cases
return taken + notTaken;
}
// Driver Code
public static void Main()
{
// Given Input
int n = 2, m = 3;
// Function Call
Console.WriteLine(countSortedArrays(1, m, 0, n));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
function countSortedArrays(start, m, size, n)
{
// If size becomes equal to m,
// that means an array is found
if (size === m)
return 1;
if (start > n)
return 0;
var notTaken = 0,
taken = 0;
// Include current element, increase
// size by 1 and remain on the same
// element as it can be included again
taken = countSortedArrays(start, m, size + 1, n);
// Exclude current element
notTaken = countSortedArrays(start + 1, m,
size, n);
// Return the sum obtained
// in both the cases
return taken + notTaken;
}
// Driver Code
// Given Input
var n = 2,
m = 3;
// Function Call
document.write(countSortedArrays(1, m, 0, n));
// This code is contributed by rdtank
</script>
Producción:
4
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque recursivo con optimización:
- Recorra cada elemento e intente encontrar todas las arrays posibles a partir de ese elemento.
- En el enfoque anterior para la rama derecha, el elemento se deja primero y, en el siguiente paso, se desplaza al siguiente elemento.
- En este enfoque, en lugar de dejar el elemento primero y luego pasar al siguiente elemento, vaya directamente al siguiente elemento, por lo que habrá menos llamadas a funciones.
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
// M-length sorted arrays possible
// using numbers from the range [1, N]
void countSortedArrays(int st, int n,
int m, int& ans, int size)
{
// If size becomes equal to m
// one sorted array is found
if (size == m) {
ans += 1;
return;
}
// Traverse over the range [st, N]
for (int i = st; i <= n; i++) {
// Find all sorted arrays
// starting from i
countSortedArrays(i, n, m,
ans, size + 1);
}
}
// Driver Code
int main()
{
// Given Input
int n = 2, m = 3;
// Store the required result
int ans = 0;
// Function Call
countSortedArrays(1, n, m, ans, 0);
// Print the result
cout << ans;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(int st, int n,
int m, int ans,
int size)
{
// If size becomes equal to m
// one sorted array is found
if (size == m)
{
ans += 1;
System.out.println(ans);
return ans;
}
// Traverse over the range [st, N]
for(int i = st; i <= n; i++)
{
// Find all sorted arrays
// starting from i
ans = countSortedArrays(i, n, m,
ans, size + 1);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int n = 2, m = 3;
// Store the required result
int ans = 0;
// Function Call
ans = countSortedArrays(1, n, m, ans, 0);
// Print the result
System.out.println(ans);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python program for the above approach # Function to find the number of # M-length sorted arrays possible # using numbers from the range [1, N] def countSortedArrays( st, n, m, ans, size): # If size becomes equal to m # one sorted array is found if (size == m): ans += 1 return ans # Traverse over the range [st, N] for i in range(st,n+1): # Find all sorted arrays # starting from i ans = countSortedArrays(i, n, m, ans, size + 1) return ans # Given Input n = 2 m = 3 # Store the required result ans = 0 # Function Call ans = countSortedArrays(1, n, m, ans, 0) # Print the result print(ans) # This code is contributed by unknown2108.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(int st, int n,
int m, int ans,
int size)
{
// If size becomes equal to m
// one sorted array is found
if (size == m)
{
ans += 1;
return ans;
}
// Traverse over the range [st, N]
for(int i = st; i <= n; i++)
{
// Find all sorted arrays
// starting from i
ans = countSortedArrays(i, n, m,
ans, size + 1);
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given Input
int n = 2, m = 3;
// Store the required result
int ans = 0;
// Function Call
ans = countSortedArrays(1, n, m, ans, 0);
// Print the result
Console.Write(ans);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
function countSortedArrays( st, n, m, ans, size)
{
// If size becomes equal to m
// one sorted array is found
if (size == m)
{
ans += 1;
return ans;
}
// Traverse over the range [st, N]
for(var i = st; i <= n; i++)
{
// Find all sorted arrays
// starting from i
ans = countSortedArrays(i, n, m, ans, size + 1);
}
return ans;
}
// Given Input
var n = 2, m = 3;
// Store the required result
var ans = 0;
// Function Call
ans = countSortedArrays(1, n, m, ans, 0);
// Print the result
document.write(ans);
// This code is contributed by SoumikMondal
</script>
Producción:
4
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque de programación dinámica : se puede observar que este problema tiene subproblemas superpuestos y una propiedad de subestructura óptima , es decir, satisface ambas propiedades de la programación dinámica. Entonces, la idea es usar una tabla 2D para memorizar los resultados durante las llamadas a funciones.
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
// M-length sorted arrays possible
// using numbers from the range [1, N]
int countSortedArrays(vector<vector<int> >& dp,
int m, int n)
{
// Base cases
if (m == 0) {
return 1;
}
if (n <= 0)
return 0;
// If the result is already computed,
// return the result of the state
if (dp[m][n] != -1)
return dp[m][n];
int taken = 0, notTaken = 0;
// Include current element, decrease
// required size by 1 and remain on the
// same element, as it can be taken again
taken = countSortedArrays(dp, m - 1, n);
// If element is not included
notTaken = countSortedArrays(dp, m, n - 1);
// Store the result and return it
return dp[m][n] = taken + notTaken;
}
// Driver Code
int main()
{
// Given Input
int n = 2, m = 3;
// Create an 2D array for memoization
vector<vector<int> > dp(m + 1,
vector<int>(n + 1, -1));
// Function Call
cout << countSortedArrays(dp, m, n);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(ArrayList<ArrayList<Integer>> dp, int m, int n)
{
// Base cases
if (m == 0) {
return 1;
}
if (n <= 0){
return 0;
}
// If the result is already computed,
// return the result of the state
if (dp.get(m).get(n) != -1){
return dp.get(m).get(n);
}
int taken = 0, notTaken = 0;
// Include current element, decrease
// required size by 1 and remain on the
// same element, as it can be taken again
taken = countSortedArrays(dp, m - 1, n);
// If element is not included
notTaken = countSortedArrays(dp, m, n - 1);
// Store the result and return it
dp.get(m).set(n, taken + notTaken);
return taken + notTaken;
}
public static void main(String args[])
{
// Given Input
int n = 2, m = 3;
// Create an 2D array for memoization
ArrayList<ArrayList<Integer>> dp = new ArrayList<ArrayList<Integer>>();
for(int i = 0 ; i <= m ; i++){
dp.add(new ArrayList<Integer>());
for(int j = 0 ; j <=n ; j++){
dp.get(i).add(-1);
}
}
// Function Call
System.out.println(countSortedArrays(dp, m, n));
}
}
// This code is contributed by subhamgoyal2014.
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(List<List<int>> dp, int m, int n)
{
// Base cases
if (m == 0) {
return 1;
}
if (n <= 0){
return 0;
}
// If the result is already computed,
// return the result of the state
if (dp[m][n] != -1){
return dp[m][n];
}
int taken = 0, notTaken = 0;
// Include current element, decrease
// required size by 1 and remain on the
// same element, as it can be taken again
taken = countSortedArrays(dp, m - 1, n);
// If element is not included
notTaken = countSortedArrays(dp, m, n - 1);
// Store the result and return it
dp[m][n] = taken + notTaken;
return taken + notTaken;
}
// Driver code
public static void Main(string[] args){
// Given Input
int n = 2, m = 3;
// Create an 2D array for memoization
List<List<int>> dp = new List<List<int>>();
for(int i = 0 ; i <= m ; i++){
dp.Add(new List<int>());
for(int j = 0 ; j <= n ; j++){
dp[i].Add(-1);
}
}
// Function Call
Console.WriteLine(countSortedArrays(dp, m, n));
}
}
// This code is contributed by entertain2022.
Producción:
4
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Enfoque de programación dinámica iterativa optimizada para el espacio :
- Como todos los elementos están disponibles tantas veces como sea necesario, por lo que no es necesario guardar los valores de las filas anteriores, se pueden usar los valores de la misma fila.
- Por lo tanto, se puede usar una array 1-D para guardar resultados anteriores.
- Cree una array , dp de tamaño M , donde dp[i] almacena la cantidad máxima de arrays ordenadas de tamaño i que se pueden formar a partir de números en el rango [1, N] .
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
// M-length sorted arrays possible
// using numbers from the range [1, N]
int countSortedArrays(int n, int m)
{
// Create an array of size M+1
vector<int> dp(m + 1, 0);
// Base cases
dp[0] = 1;
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// dp[j] will be equal to maximum
// number of sorted array of size j
// when elements are taken from 1 to i
dp[j] = dp[j - 1] + dp[j];
}
// Here dp[m] will be equal to the
// maximum number of sorted arrays when
// element are taken from 1 to i
}
// Return the result
return dp[m];
}
// Driver Code
int main()
{
// Given Input
int n = 2, m = 3;
// Function Call
cout << countSortedArrays(n, m);
return 0;
}
Java
// Java program for the above approach
public class Main
{
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(int n, int m)
{
// Create an array of size M+1
int[] dp = new int[(m + 1)];
// Base cases
dp[0] = 1;
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// dp[j] will be equal to maximum
// number of sorted array of size j
// when elements are taken from 1 to i
dp[j] = dp[j - 1] + dp[j];
}
// Here dp[m] will be equal to the
// maximum number of sorted arrays when
// element are taken from 1 to i
}
// Return the result
return dp[m];
}
// Driver code
public static void main(String[] args)
{
// Given Input
int n = 2, m = 3;
// Function Call
System.out.print(countSortedArrays(n, m));
}
}
// This code is contributed by suresh07.
Python3
# Python program for the above approach # Function to find the number of # M-length sorted arrays possible # using numbers from the range [1, N] def countSortedArrays(n, m): # Create an array of size M+1 dp = [0 for _ in range(m + 1)] # Base cases dp[0] = 1 # Fill the dp table for i in range(1, n + 1): for j in range(1, m + 1): # dp[j] will be equal to maximum # number of sorted array of size j # when elements are taken from 1 to i dp[j] = dp[j - 1] + dp[j] # Here dp[m] will be equal to the # maximum number of sorted arrays when # element are taken from 1 to i # Return the result return dp[m] # Driver code # Given Input n = 2 m = 3 # Function Call print (countSortedArrays(n, m)) # This code is contributed by rdtank.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
static int countSortedArrays(int n, int m)
{
// Create an array of size M+1
int[] dp = new int[(m + 1)];
// Base cases
dp[0] = 1;
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// dp[j] will be equal to maximum
// number of sorted array of size j
// when elements are taken from 1 to i
dp[j] = dp[j - 1] + dp[j];
}
// Here dp[m] will be equal to the
// maximum number of sorted arrays when
// element are taken from 1 to i
}
// Return the result
return dp[m];
}
// Driver Code
public static void Main()
{
// Given Input
int n = 2, m = 3;
// Function Call
Console.WriteLine(countSortedArrays(n, m));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of
// M-length sorted arrays possible
// using numbers from the range [1, N]
function countSortedArrays(n, m)
{
// Create an array of size M+1
let dp = new Array(m + 1);
dp.fill(0);
// Base cases
dp[0] = 1;
// Fill the dp table
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// dp[j] will be equal to maximum
// number of sorted array of size j
// when elements are taken from 1 to i
dp[j] = dp[j - 1] + dp[j];
}
// Here dp[m] will be equal to the
// maximum number of sorted arrays when
// element are taken from 1 to i
}
// Return the result
return dp[m];
}
// Given Input
let n = 2, m = 3;
// Function Call
document.write(countSortedArrays(n, m));
</script>
Producción:
4
Complejidad temporal: O(N*M)
Espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por sachinjain74754 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA