# Count L-length arrays possible made up of first N natural numbers and each element dividing the next element

Given two positive integers **N** and **L**, the task is to find the number of **L**-length arrays made up of first **N** natural numbers such that every element in the array divides its next element.

**Examples:**

Input:N = 3, L = 3Output:7Explanation:

Following arrays has elements from the range [1, 3] and each array element divides its next element:

- {1, 1, 1}
- {1, 1, 2}
- {1, 2, 2}
- {1, 1, 3}
- {1, 3, 3}
- {2, 2, 2}
- {3, 3, 3}
Therefore, the count of arrays is 7.

Input:N = 2, L = 4Output:5

**Approach:** The given problem can be solved by using Dynamic Programming and the idea of Sieve of Eratosthenes. Follow the steps below to solve the problem:

- Initialize a 2D array
**dp[][]**where**dp[i][j]**denotes the number of sequences of length**i**that ends with**j**and initialize**dp[0][1]**as**1**. - Iterate over the range
**[0, L – 1]**using the variable**i**and nested iterate over the range**[1, N]**using the variable**j**:- As the next element of the constructed array should be multiple of the current element, therefore iterate over the range
**[j, N]**with an increment of**j**and update the value of**dp[i + 1][k]**to the value**dp[i][j] + dp[i + 1][k]**.

- As the next element of the constructed array should be multiple of the current element, therefore iterate over the range
- Initialize a variable, say
**answer**as**0**that stores the resultant number of arrays. - Iterate over the range
**[1, N]**and add the value of**dp[L][i]**to the variable**ans**. - After completing the above steps, print the value of
**ans**as the result.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Fumction to find the number of` `// arrays of length L such that each` `// element divides the next element` `int` `numberOfArrays(` `int` `n, ` `int` `l)` `{` ` ` `// Stores the number of sequences` ` ` `// of length i that ends with j` ` ` `int` `dp[l + 1][n + 1];` ` ` `// Initialize 2D array dp[][] as 0` ` ` `memset` `(dp, 0, ` `sizeof` `dp);` ` ` `// Base Case` ` ` `dp[0][1] = 1;` ` ` `// Iterate over the range [0, l]` ` ` `for` `(` `int` `i = 0; i < l; i++) {` ` ` `for` `(` `int` `j = 1; j <= n; j++) {` ` ` `// Iterate for all multiples` ` ` `// of j` ` ` `for` `(` `int` `k = j; k <= n; k += j) {` ` ` `// Incrementing dp[i+1][k]` ` ` `// by dp[i][j] as the next` ` ` `// element is multiple of j` ` ` `dp[i + 1][k] += dp[i][j];` ` ` `}` ` ` `}` ` ` `}` ` ` `// Stores the number of arrays` ` ` `int` `ans = 0;` ` ` `for` `(` `int` `i = 1; i <= n; i++) {` ` ` `// Add all array of length` ` ` `// L that ends with i` ` ` `ans += dp[l][i];` ` ` `}` ` ` `// Return the resultant count` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 2, L = 4;` ` ` `cout << numberOfArrays(N, L);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` ` ` `static` `int` `numberOfArrays(` `int` `n, ` `int` `l)` ` ` `{` ` ` `// Stores the number of sequences` ` ` `// of length i that ends with j` ` ` `int` `[][] dp=` `new` `int` `[l + ` `1` `][n + ` `1` `];` ` ` ` ` ` ` ` ` ` ` `// Base Case` ` ` `dp[` `0` `][` `1` `] = ` `1` `;` ` ` ` ` `// Iterate over the range [0, l]` ` ` `for` `(` `int` `i = ` `0` `; i < l; i++) {` ` ` `for` `(` `int` `j = ` `1` `; j <= n; j++) {` ` ` ` ` `// Iterate for all multiples` ` ` `// of j` ` ` `for` `(` `int` `k = j; k <= n; k += j) {` ` ` ` ` `// Incrementing dp[i+1][k]` ` ` `// by dp[i][j] as the next` ` ` `// element is multiple of j` ` ` `dp[i + ` `1` `][k] += dp[i][j];` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Stores the number of arrays` ` ` `int` `ans = ` `0` `;` ` ` ` ` `for` `(` `int` `i = ` `1` `; i <= n; i++) {` ` ` ` ` `// Add all array of length` ` ` `// L that ends with i` ` ` `ans += dp[l][i];` ` ` `}` ` ` ` ` `// Return the resultant count` ` ` `return` `ans;` ` ` `}` ` ` ` ` `// Driver Code` ` ` `public` `static` `void` `main (String[] args) {` ` ` ` ` `int` `N = ` `2` `, L = ` `4` `;` ` ` `System.out.println(numberOfArrays(N, L));` ` ` `}` `}` `// This code is contributed by unknown2108` |

## Python3

`# Python3 program for the above approach` `# Function to find the number of` `# arrays of length L such that each` `# element divides the next element` `def` `numberOfArrays(n, l):` ` ` ` ` `# Stores the number of sequences` ` ` `# of length i that ends with j` ` ` `dp ` `=` `[[` `0` `for` `i ` `in` `range` `(n ` `+` `1` `)]` ` ` `for` `i ` `in` `range` `(l ` `+` `1` `)]` ` ` `# Initialize 2D array dp[][] as 0a` ` ` `# memset(dp, 0, sizeof dp)` ` ` `# Base Case` ` ` `dp[` `0` `][` `1` `] ` `=` `1` ` ` `# Iterate over the range [0, l]` ` ` `for` `i ` `in` `range` `(l):` ` ` `for` `j ` `in` `range` `(` `1` `, n ` `+` `1` `):` ` ` ` ` `# Iterate for all multiples` ` ` `# of j` ` ` `for` `k ` `in` `range` `(j, n ` `+` `1` `, j):` ` ` ` ` `# Incrementing dp[i+1][k]` ` ` `# by dp[i][j] as the next` ` ` `# element is multiple of j` ` ` `dp[i ` `+` `1` `][k] ` `+` `=` `dp[i][j]` ` ` `# Stores the number of arrays` ` ` `ans ` `=` `0` ` ` `for` `i ` `in` `range` `(` `1` `, n ` `+` `1` `):` ` ` ` ` `# Add all array of length` ` ` `# L that ends with i` ` ` `ans ` `+` `=` `dp[l][i]` ` ` `# Return the resultant count` ` ` `return` `ans` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `N, L ` `=` `2` `, ` `4` ` ` ` ` `print` `(numberOfArrays(N, L))` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Fumction to find the number of` `// arrays of length L such that each` `// element divides the next element` `static` `int` `numberOfArrays(` `int` `n, ` `int` `l)` `{` ` ` `// Stores the number of sequences` ` ` `// of length i that ends with j` ` ` `int` `[,]dp = ` `new` `int` `[l + 1,n + 1];` ` ` `// Initialize 2D array dp[][] as 0` ` ` `for` `(` `int` `i = 0; i < l + 1; i++){` ` ` `for` `(` `int` `j = 0; j < n + 1; j++)` ` ` `dp[i, j] = 0;` ` ` `}` ` ` `// Base Case` ` ` `dp[0, 1] = 1;` ` ` `// Iterate over the range [0, l]` ` ` `for` `(` `int` `i = 0; i < l; i++) {` ` ` `for` `(` `int` `j = 1; j <= n; j++) {` ` ` `// Iterate for all multiples` ` ` `// of j` ` ` `for` `(` `int` `k = j; k <= n; k += j) {` ` ` `// Incrementing dp[i+1][k]` ` ` `// by dp[i][j] as the next` ` ` `// element is multiple of j` ` ` `dp[i + 1,k] += dp[i,j];` ` ` `}` ` ` `}` ` ` `}` ` ` `// Stores the number of arrays` ` ` `int` `ans = 0;` ` ` `for` `(` `int` `i = 1; i <= n; i++) {` ` ` `// Add all array of length` ` ` `// L that ends with i` ` ` `ans += dp[l,i];` ` ` `}` ` ` `// Return the resultant count` ` ` `return` `ans;` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 2, L = 4;` ` ` `Console.Write(numberOfArrays(N, L));` `}` `}` `// This code is contributed by SURENDRA_GANGWAR.` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Fumction to find the number of` `// arrays of length L such that each` `// element divides the next element` `function` `numberOfArrays(n, l)` `{` ` ` ` ` `// Stores the number of sequences` ` ` `// of length i that ends with j` ` ` ` ` `let dp= Array(l+1).fill().map(() =>` ` ` `Array(n+1).fill(0));` ` ` ` ` `// Initialize 2D array dp[][] as 0` ` ` ` ` ` ` `// Base Case` ` ` `dp[0][1] = 1;` ` ` ` ` `// Iterate over the range [0, l]` ` ` `for` `(let i = 0; i < l; i++) {` ` ` `for` `(let j = 1; j <= n; j++) {` ` ` ` ` `// Iterate for all multiples` ` ` `// of j` ` ` `for` `(let k = j; k <= n; k += j) {` ` ` ` ` `// Incrementing dp[i+1][k]` ` ` `// by dp[i][j] as the next` ` ` `// element is multiple of j` ` ` `dp[i + 1][k] += dp[i][j];` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Stores the number of arrays` ` ` `let ans = 0;` ` ` ` ` `for` `(let i = 1; i <= n; i++) {` ` ` ` ` `// Add all array of length` ` ` `// L that ends with i` ` ` `ans += dp[l][i];` ` ` `}` ` ` ` ` `// Return the resultant count` ` ` `return` `ans;` `}` ` ` `// Driver Code` ` ` `let N = 2, L = 4;` ` ` `document.write( numberOfArrays(N, L));` ` ` `// This code is contributed by` `// Potta Lokesh` ` ` `</script>` |

**Output:**

5

**Time Complexity:** O(N*L*log N)**Auxiliary Space:** O(N*L)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.