# Count of divisible array

Count of divisible array: This is a standard recursion problem that can be featured in any interview rounds or competitive programming challenges.
Submitted by Radib Kar, on June 08, 2020

Problem statement:

Given two positive integer n and m, find how many arrays of size n that can be formed such that:

1. Each element of the array is in the range [1, m]
2. Any adjacent element pair is divisible, i.e., that one of them divides another. Either element A[i] divides A[i + 1] or A[i + 1] divides A[i].

Input:

Only one line with two integer, n & m respectively.

Output:

Print number of different possible ways to create the array. Since the output could be long take modulo 10^9+7.

Constraints:

```1<=n, m<=100
```

Example:

```    Input:
n = 3, m = 2.

Output:
8

Explanation:
{1,1,1},{1, 1, 2}, {1, 2, 1},
{1, 2, 2}, {2, 1, 1},
{2,1,2},  {2,2,1}, {2,2,2} are possible arrays.

Input:
n = 1, m = 5.

Output:
5
Explanation:
{1}, {2}, {3}, {4}, {5}
```

Solution Approach:

The above problem is a great example of recursion. What can be the recursive function and how we can formulate.

Say,

Let

F(n, m) = number of ways for array size n and range 1 to m

Now,

We actually can try picking every element from raging 1 to m and try recurring for other elements

So, the function can be written like:

```Function: NumberofWays(cur_index,lastelement,n,m)
```

So, to describe the arguments,

cur_index is your current index and the last element is the previous index value assigned. So basically need to check which value with range 1 to m fits in the cur_index such that the divisibility constraint satisfies.

So, to describe the body of the function

```Function NumberofWays(cur_index,lastelement,n,m)
// formed the array completely
if(cur_index==n)
return 1;
sum=0

// any element in the range
for j=1 to m
// if divisible then lastelement,
// j can be adjacent pair
if(j%lastelement==0 || lastelement%j==0)
// recur for rest of the elments
sum=(sum%MOD+ NumberofWays(cur_index+1,j,n,m)%MOD)%MOD;
end if
end for
End function
```

Now the above recursive function generates many overlapping sub-problem and that's why we use the top-down DP approach to store already computed sub-problem results.
Below is the implementation with adding memoization.

Initiate a 2D DP array with -1

```Function NumberofWays(cur_index,lastelement,n,m)
// formed the array completely
if(cur_index==n)
return 1;
// if solution to sub problem already exits
if(dp[cur_index][lastelement]!=-1)
return dpdp[cur_index][lastelement];
sum=0
for j=1 to m // any element in the range
// if divisible then lastelement,j can be adjacent pair
if(j%lastelement==0 || lastelement%j==0)
// recur for rest of the elments
sum=(sum%MOD+ NumberofWays(cur_index+1,j,n,m)%MOD)%MOD;
end if
end for
Dp[curindex][lastelement]=sum
Return Dp[curindex][lastelement]
End function
```

C++ Implementation:

```#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

int dp;

int countarray(int index, int i, int n, int m)
{
// if solution to sub problem already exits
if (dp[index][i] != -1)
return dp[index][i];

if (index == n)
return 1;
int sum = 0;

//any element in the range
for (int j = 1; j <= m; j++) {
// if divisible then i,j can be adjacent pair
if (j % i == 0 || i % j == 0) {
// recur for rest of the elments
sum = (sum % MOD + countarray(index + 1, j, n, m) % MOD) % MOD;
}
}
dp[index][i] = sum;
return dp[index][i];
}

int main()
{
int n, m;

cout << "Enter value of n:\n";
cin >> n;
cout << "Enter value of m:\n";
cin >> m;

// initialize DP matrix
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = -1;
}
}

cout << "number of ways are: " << countarray(0, 1, n, m) << endl;

return 0;
}
```

Output:

```Enter value of n:
3
Enter value of m:
2
number of ways are: 8
```

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates