Given two integer N and K, the task is to find the number of sequence of length K consisting of values from the range [1, N], such that every (i + 1)th element in the sequence is divisible by its preceding ith element.
Examples:
Input: N = 3, K = 2
Output: 5
Explanation:
The 5 sequence are [1, 1], [2, 2], [3, 3], [1, 2], [1, 3]Input: N = 6 K= 4
Output: 39
Approach:
Follow the steps below to solve the problem:
- Initialize a matrix fct[][] and store the factors of i in the row fct[i], where i lies in the range [1, N].
- Initialize a matrix dp[][], which stores at dp[i][j], the number of sequences of length i ending with j.
- If ith index has j, (i – 1)th index should consist of factor(j). Similarly, (i – 2)th index should consist of a factor(factor(j)).
- Hence, dp[i][j] should comprise of all possible sequences of (i – 1) length ending with a factor of j.
- Hence, dp[i][j] is equal to the sum of all possible dp[i – 1][fct[j][k]], where dp[i – 1][fct[j][k]] denotes the count of total sequences of length i – 1 ending with kth factor of j.
- Finally, find the sum of all dp[K][j] from 1<=j<=N and return the sum.
Below is the implementation of the above approach:
C++14
// C++ Program to implement the// above approach#include <bits/stdc++.h>using namespace std;#define ll long long// Stores the factors of i-th// element in v[i]vector<ll int> vp[2009];// Function to find all the// factors of Nvoid finding_factors(ll int n){ ll int i, a; // Iterate upto sqrt(N) for (i = 1; i * i <= n; i++) { if (n % i == 0) { if (i * i == n) { vp[n].push_back(i); } else { vp[n].push_back(i); vp[n].push_back(n / i); } } }}// Function to return the count of// sequences of length K having// all terms divisible by its// preceding termll int countSeq(ll int N, ll int K){ ll int i, j, k; ll int dp[109][109] = { 0 }; for (i = 1; i <= N; i++) { // Calculate factors of i finding_factors(i); // Initialize dp[0][i] = 0: No // subsequence of length 0 ending // with i-th element exists dp[0][i] = 0; // Initialize dp[0][i] = 1: Only 1 // subsequence of length 1 ending // with i-th element exists dp[1][i] = 1; } // Iterate [2, K] to obtain sequences // of each length for (i = 2; i <= K; i++) { for (j = 1; j <= N; j++) { // Calculate sum of // all dp[i-1][vp[j][k]] ll int sum = 0; for (k = 0; k < vp[j].size(); k++) { // vp[j][k] stores all factors // of j sum = (sum + dp[i - 1][vp[j][k]]); } // Store the sum in A[i][j] dp[i][j] = sum; } } ll int ans = 0; for (j = 1; j <= N; j++) { // Sum of all dp[K][j] obtain all // K length sequences ending with j ans = (ans + dp[K][j]); } return ans;}// Driver codeint main(){ ll int N, K; N = 3; K = 2; cout << countSeq(N, K) << endl; return 0;} |
Java
// Java program to implement the// above approachimport java.util.*;class GFG{// Stores the factors of i-th// element in v[i]@SuppressWarnings("unchecked")static Vector<Integer> []vp = new Vector[2009];// Function to find all the// factors of Nstatic void finding_factors(int n){ int i, a; // Iterate upto Math.sqrt(N) for(i = 1; i * i <= n; i++) { if (n % i == 0) { if (i * i == n) { vp[n].add(i); } else { vp[n].add(i); vp[n].add(n / i); } } }}// Function to return the count of// sequences of length K having// all terms divisible by its// preceding termstatic int countSeq(int N, int K){ int i, j, k; int dp[][] = new int[109][109]; for(i = 1; i <= N; i++) { // Calculate factors of i finding_factors(i); // Initialize dp[0][i] = 0: No // subsequence of length 0 ending // with i-th element exists dp[0][i] = 0; // Initialize dp[0][i] = 1: Only 1 // subsequence of length 1 ending // with i-th element exists dp[1][i] = 1; } // Iterate [2, K] to obtain sequences // of each length for(i = 2; i <= K; i++) { for(j = 1; j <= N; j++) { // Calculate sum of // aint dp[i-1][vp[j][k]] int sum = 0; for(k = 0; k < vp[j].size(); k++) { // vp[j][k] stores aint factors // of j sum = (sum + dp[i - 1][vp[j].get(k)]); } // Store the sum in A[i][j] dp[i][j] = sum; } } int ans = 0; for(j = 1; j <= N; j++) { // Sum of aint dp[K][j] obtain all // K length sequences ending with j ans = (ans + dp[K][j]); } return ans;}// Driver codepublic static void main(String[] args){ int N, K; N = 3; K = 2; for(int i = 0; i < vp.length; i++) vp[i] = new Vector<Integer>(); System.out.print(countSeq(N, K) + "\n");}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to implement the# above approach# Stores the factors of i-th# element in v[i]vp = [[] for i in range(2009)]# Function to find all the# factors of Ndef finding_factors(n): i = 1 a = 0 global vp # Iterate upto sqrt(N) while (i * i <= n): if (n % i == 0): if (i * i == n): vp[n].append(i) else: vp[n].append(i) vp[n].append(int(n / i)) i += 1# Function to return the count of# sequences of length K having# all terms divisible by its# preceding termdef countSeq(N, K): i = 0 j = 0 k = 0 dp = [[0 for i in range(109)] for j in range(109)] for i in range(1, N + 1): # Calculate factors of i finding_factors(i) # Initialize dp[0][i] = 0: No # subsequence of length 0 ending # with i-th element exists dp[0][i] = 0 # Initialize dp[0][i] = 1: Only 1 # subsequence of length 1 ending # with i-th element exists dp[1][i] = 1 # Iterate [2, K] to obtain sequences # of each length for i in range(2, K + 1): for j in range(1, N + 1): # Calculate sum of # all dp[i-1][vp[j][k]] Sum = 0 for k in range(len(vp[j])): # vp[j][k] stores all factors # of j Sum += dp[i - 1][vp[j][k]] # Store the sum in A[i][j] dp[i][j] = Sum ans = 0 for j in range(1, N + 1): # Sum of all dp[K][j] obtain all # K length sequences ending with j ans += dp[K][j] return ans# Driver codeN = 3K = 2print(countSeq(N, K))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program to implement the// above approachusing System;using System.Collections.Generic;class GFG{// Stores the factors of i-th// element in v[i]static List<int> []vp = new List<int>[2009];// Function to find all the// factors of Nstatic void finding_factors(int n){ int i ; // Iterate upto Math.Sqrt(N) for(i = 1; i * i <= n; i++) { if (n % i == 0) { if (i * i == n) { vp[n].Add(i); } else { vp[n].Add(i); vp[n].Add(n / i); } } }}// Function to return the count of// sequences of length K having// all terms divisible by its// preceding termstatic int countSeq(int N, int K){ int i, j, k; int [,]dp = new int[109, 109]; for(i = 1; i <= N; i++) { // Calculate factors of i finding_factors(i); // Initialize dp[0,i] = 0: No // subsequence of length 0 ending // with i-th element exists dp[0, i] = 0; // Initialize dp[0,i] = 1: Only 1 // subsequence of length 1 ending // with i-th element exists dp[1, i] = 1; } // Iterate [2, K] to obtain sequences // of each length for(i = 2; i <= K; i++) { for(j = 1; j <= N; j++) { // Calculate sum of // aint dp[i-1,vp[j,k]] int sum = 0; for(k = 0; k < vp[j].Count; k++) { // vp[j,k] stores aint factors // of j sum = (sum + dp[i - 1, vp[j][k]]); } // Store the sum in A[i,j] dp[i,j] = sum; } } int ans = 0; for(j = 1; j <= N; j++) { // Sum of aint dp[K,j] obtain all // K length sequences ending with j ans = (ans + dp[K, j]); } return ans;}// Driver codepublic static void Main(String[] args){ int N, K; N = 3; K = 2; for(int i = 0; i < vp.Length; i++) vp[i] = new List<int>(); Console.Write(countSeq(N, K) + "\n");}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// JavaScript program to implement the// above approach// Stores the factors of i-th// element in v[i]let vp = new Array(2009);// Function to find all the// factors of Nfunction finding_factors(n){ let i, a; // Iterate upto Math.sqrt(N) for(i = 1; i * i <= n; i++) { if (n % i == 0) { if (i * i == n) { vp[n].push(i); } else { vp[n].push(i); vp[n].push(n / i); } } }}// Function to return the count of// sequences of length K having// all terms divisible by its// preceding termfunction countSeq(N, K){ let i, j, k; let dp = new Array(109); // Loop to create 2D array using 1D array for (let i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for(i = 1; i <= N; i++) { // Calculate factors of i finding_factors(i); // Initialize dp[0][i] = 0: No // subsequence of length 0 ending // with i-th element exists dp[0][i] = 0; // Initialize dp[0][i] = 1: Only 1 // subsequence of length 1 ending // with i-th element exists dp[1][i] = 1; } // Iterate [2, K] to obtain sequences // of each length for(i = 2; i <= K; i++) { for(j = 1; j <= N; j++) { // Calculate sum of // alet dp[i-1][vp[j][k]] let sum = 0; for(k = 0; k < vp[j].length; k++) { // vp[j][k] stores alet factors // of j sum = (sum + dp[i - 1][vp[j][k]]); } // Store the sum in A[i][j] dp[i][j] = sum; } } let ans = 0; for(j = 1; j <= N; j++) { // Sum of alet dp[K][j] obtain all // K length sequences ending with j ans = (ans + dp[K][j]); } return ans;}// Driver Code let N, K; N = 3; K = 2; for(let i = 0; i < vp.length; i++) vp[i] = []; document.write(countSeq(N, K) + "\n");</script> |
Output:
5
Time Complexity: O (K * N 3/2)
Auxiliary Space: O (N 2)
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!
