Given two integers N and K, the task is to find the count of sequences of K elements from the range [1, N] where every element is a multiple of the previous element.
Example:
Input: N = 4, K = 3
Output: 13
Explanation: The sequences that can be made from the integers 1, 2, 3, 4 having 3 elements are: {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}, and {2, 4, 4}.Input: N = 9, K = 5
Output: 111
Approach: The given problem can be solved using recursion with memoization. Follow the below steps to solve the problem:
- Create a 2D array dp[][] which stores the memorized states where dp[i][j] represents the count of sequences of length i having j as their first element.
- Create a recursive function countSequenceUtil(), that takes the length of the sequence and the starting element as arguments, sets the next element as a multiple of the current element, and recursively calls for the remaining sequence.
- Store the answer for the calculated states in the dp[][] array and if for some state the value is already calculated, return it.
- Create a function countSequence() which iterates through all the possible starting elements of the sequence and calls the recursive function to calculate the sequences of K elements with that starting element.
- Maintain the sum of the calculated count for each starting element in a variable ans which is the required value.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Initialize the dp matrixint 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 oneint 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 oneint 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 Codeint main(){ int N = 9; int K = 5; cout << countSequence(N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Initialize the dp matrixstatic 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 onestatic 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 onestatic 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 matrixdp = [[-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 onedef 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 onedef 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 CodeN = 9K = 5print(countSequence(N, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing 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> |
Output
111
Time Complexity: O(N*K*log N)
Auxiliary Space: O(N*K)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation :
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of sequences of K// elements with first element as m where every// element is a multiple of the previous oneint countSequence(int N, int K){ // Initialize the dp matrix int dp[K + 1][N + 1]; // Base case for (int i = 1; i <= N; i++) { dp[1][i] = 1; } // Tabulate the dp matrix for (int k = 2; k <= K; k++) { for (int m = 1; m <= N; m++) { dp[k][m] = 0; for (int i = 1; i <= (N / m); i++) { dp[k][m] += dp[k - 1][m * i]; } } } // Compute the final result int ans = 0; for (int i = 1; i <= N; i++) { ans += dp[K][i]; } // Return the answer return ans;}// Driver Codeint main(){ int N = 9; int K = 5; cout << countSequence(N, K); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // 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 countSequence(int N, int K) { // Initialize the dp matrix int[][] dp = new int[K + 1][N + 1]; // Base case for (int i = 1; i <= N; i++) { dp[1][i] = 1; } // Tabulate the dp matrix for (int k = 2; k <= K; k++) { for (int m = 1; m <= N; m++) { dp[k][m] = 0; for (int i = 1; i <= (N / m); i++) { dp[k][m] += dp[k - 1][m * i]; } } } // Compute the final result int ans = 0; for (int i = 1; i <= N; i++) { ans += dp[K][i]; } // Return the answer 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 Gaurav_Arora |
Python3
def countSequence(N, K): # Initialize the dp matrix dp = [[0 for i in range(N + 1)] for j in range(K + 1)] # Base case for i in range(1, N + 1): dp[1][i] = 1 # Tabulate the dp matrix for k in range(2, K + 1): for m in range(1, N + 1): dp[k][m] = 0 for i in range(1, (N // m) + 1): dp[k][m] += dp[k - 1][m * i] # Compute the final result ans = 0 for i in range(1, N + 1): ans += dp[K][i] # Return the answer return ans # Driver Code if __name__ == "__main__": N = 9 K = 5 print(countSequence(N, K)) |
C#
// C# program for above approachusing System;public class GFG{ // 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 CountSequence(int N, int K) { // Initialize the dp matrix int[,] dp = new int[K + 1, N + 1]; // Base case for (int i = 1; i <= N; i++) { dp[1, i] = 1; } // Tabulate the dp matrix for (int k = 2; k <= K; k++) { for (int m = 1; m <= N; m++) { dp[k, m] = 0; for (int i = 1; i <= (N / m); i++) { dp[k, m] += dp[k - 1, m * i]; } } } // Compute the final result int ans = 0; for (int i = 1; i <= N; i++) { ans += dp[K, i]; } // Return the answer return ans; } // Driver Code public static void Main(string[] args) { int N = 9; int K = 5; Console.WriteLine(CountSequence(N, K)); }} |
Javascript
// Function to find the count of sequences of K// elements with first element as m where every// element is a multiple of the previous onefunction countSequence(N, K) { // Initialize the dp matrix let dp = new Array(K + 1); for (let i = 0; i <= K; i++) { dp[i] = new Array(N + 1); } // Base case for (let i = 1; i <= N; i++) { dp[1][i] = 1; } // Tabulate the dp matrix for (let k = 2; k <= K; k++) { for (let m = 1; m <= N; m++) { dp[k][m] = 0; for (let i = 1; i <= (N / m); i++) { dp[k][m] += dp[k - 1][m * i]; } } } // Compute the final result let ans = 0; for (let i = 1; i <= N; i++) { ans += dp[K][i]; } // Return the answer return ans;}// Driver Codelet N = 9;let K = 5;console.log(countSequence(N, K)); |
Output
111
Time Complexity: O(N*K*log N)
Auxiliary Space: O(N*K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!