Dados dos números enteros N y K, la tarea es encontrar el conteo de secuencias de K elementos del rango [1, N] donde cada elemento es un múltiplo del elemento anterior.
Ejemplo:
Entrada: N = 4, K = 3
Salida: 13
Explicación: Las secuencias que se pueden hacer de los números enteros 1, 2, 3, 4 que tienen 3 elementos son: {1, 1, 1}, {2, 2, 2} , {3, 3, 3}, {4, 4, 4}, {1, 1, 2}, {1, 2, 2}, {1, 2, 4}, {1, 1, 3}, { 1, 3, 3}, {1, 1, 4}, {1, 4, 4}, {2, 2, 4} y {2, 4, 4}.Entrada: N = 9, K = 5
Salida: 111
Enfoque: El problema dado se puede resolver usando recursividad con memorización . Siga los pasos a continuación para resolver el problema:
- Cree una array 2D dp[][] que almacene los estados memorizados donde dp[i][j] representa el recuento de secuencias de longitud i que tienen j como su primer elemento.
- Cree una función recursiva countSequenceUtil() , que tome la longitud de la secuencia y el elemento inicial como argumentos, establezca el siguiente elemento como un múltiplo del elemento actual y llame recursivamente a la secuencia restante.
- Almacene la respuesta para los estados calculados en la array dp[][] y si para algún estado el valor ya está calculado, devuélvalo.
- Cree una función countSequence() que recorre en iteración todos los posibles elementos iniciales de la secuencia y llama a la función recursiva para calcular las secuencias de K elementos con ese elemento inicial.
- Mantenga la suma del recuento calculado para cada elemento inicial en una variable y cuál es el valor requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Initialize the dp matrix
int static dp[1001][1001];
// Function to find the count of sequences of K
// elements with first element as m where every
// element is a multiple of the previous one
int countSequenceUtil(int k, int m, int n)
{
// Base case
if (k == 1) {
return 1;
}
// If the value already exists
// in the DP then return it
if (dp[k][m] != -1) {
return dp[k][m];
}
// Variable to store the count
int res = 0;
for (int i = 1; i <= (n / m); i++) {
// Recursive Call
res += countSequenceUtil(k - 1,
m * i, n);
}
// Store the calculated
// answer and return it
return dp[k][m] = res;
}
// Function to find count of sequences of K
// elements in the range [1, n] where every
// element is a multiple of the previous one
int countSequence(int N, int K)
{
// Initializing all values
// of dp with -1
memset(dp, -1, sizeof(dp));
// Variable to store
// the total count
int ans = 0;
// Iterate from 1 to N
for (int i = 1; i <= N; i++) {
ans += countSequenceUtil(K, i, N);
}
// Return ans
return ans;
}
// Driver Code
int main()
{
int N = 9;
int K = 5;
cout << countSequence(N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Initialize the dp matrix
static int dp[][] = new int[1001][1001];
// Function to find the count of sequences of K
// elements with first element as m where every
// element is a multiple of the previous one
static int countSequenceUtil(int k, int m, int n)
{
// Base case
if (k == 1) {
return 1;
}
// If the value already exists
// in the DP then return it
if (dp[k][m] != -1) {
return dp[k][m];
}
// Variable to store the count
int res = 0;
for (int i = 1; i <= (n / m); i++) {
// Recursive Call
res += countSequenceUtil(k - 1,
m * i, n);
}
// Store the calculated
// answer and return it
return dp[k][m] = res;
}
// Function to find count of sequences of K
// elements in the range [1, n] where every
// element is a multiple of the previous one
static int countSequence(int N, int K)
{
// Initializing all values
// of dp with -1
for(int i=0;i<dp.length;i++)
{
for(int j=0;j<dp[i].length;j++)
{
dp[i][j]=-1;
}
}
// Variable to store
// the total count
int ans = 0;
// Iterate from 1 to N
for (int i = 1; i <= N; i++) {
ans += countSequenceUtil(K, i, N);
}
// Return ans
return ans;
}
// Driver Code
public static void main (String[] args) {
int N = 9;
int K = 5;
System.out.println(countSequence(N, K));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation for the above approach # Initialize the dp matrix dp = [[-1 for i in range(1001)] for j in range(1001)] # Function to find the count of sequences of K # elements with first element as m where every # element is a multiple of the previous one def countSequenceUtil(k, m, n): # Base case if (k == 1): return 1 # If the value already exists # in the DP then return it if (dp[k][m] != -1): return dp[k][m] # Variable to store the count res = 0 for i in range(1, (n // m) + 1): # Recursive Call res += countSequenceUtil(k - 1, m * i, n) # Store the calculated # answer and return it dp[k][m] = res return dp[k][m] # Function to find count of sequences of K # elements in the range [1, n] where every # element is a multiple of the previous one def countSequence(N, K): # Variable to store # the total count ans = 0 # Iterate from 1 to N for i in range(1, N + 1): ans += countSequenceUtil(K, i, N) # Return ans return ans # Driver Code N = 9 K = 5 print(countSequence(N, K)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG {
// Initialize the dp matrix
static int[, ] dp = new int[1001, 1001];
// Function to find the count of sequences of K
// elements with first element as m where every
// element is a multiple of the previous one
static int countSequenceUtil(int k, int m, int n)
{
// Base case
if (k == 1) {
return 1;
}
// If the value already exists
// in the DP then return it
if (dp[k, m] != -1) {
return dp[k, m];
}
// Variable to store the count
int res = 0;
for (int i = 1; i <= (n / m); i++) {
// Recursive Call
res += countSequenceUtil(k - 1, m * i, n);
}
// Store the calculated
// answer and return it
return dp[k, m] = res;
}
// Function to find count of sequences of K
// elements in the range [1, n] where every
// element is a multiple of the previous one
static int countSequence(int N, int K)
{
// Initializing all values
// of dp with -1
for (int i = 0; i < dp.GetLength(0); i++) {
for (int j = 0; j < dp.GetLength(1); j++) {
dp[i, j] = -1;
}
}
// Variable to store
// the total count
int ans = 0;
// Iterate from 1 to N
for (int i = 1; i <= N; i++) {
ans += countSequenceUtil(K, i, N);
}
// Return ans
return ans;
}
// Driver Code
public static void Main(string[] args)
{
int N = 9;
int K = 5;
Console.WriteLine(countSequence(N, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript implementation for the above approach
// Initialize the dp matrix
let dp = new Array(1001).fill(-1).map(() => new Array(1001).fill(-1));
// Function to find the count of sequences of K
// elements with first element as m where every
// element is a multiple of the previous one
const countSequenceUtil = (k, m, n) => {
// Base case
if (k == 1) {
return 1;
}
// If the value already exists
// in the DP then return it
if (dp[k][m] != -1) {
return dp[k][m];
}
// Variable to store the count
let res = 0;
for (let i = 1; i <= parseInt(n / m); i++) {
// Recursive Call
res += countSequenceUtil(k - 1,
m * i, n);
}
// Store the calculated
// answer and return it
return dp[k][m] = res;
}
// Function to find count of sequences of K
// elements in the range [1, n] where every
// element is a multiple of the previous one
const countSequence = (N, K) => {
// Variable to store
// the total count
let ans = 0;
// Iterate from 1 to N
for (let i = 1; i <= N; i++) {
ans += countSequenceUtil(K, i, N);
}
// Return ans
return ans;
}
// Driver Code
let N = 9;
let K = 5;
document.write(countSequence(N, K));
// This code is contributed by rakeshsahni
</script>
Producción
111
Complejidad de tiempo: O(N*K*log N)
Espacio auxiliar: O(N*K)