Home » Interview coding problems/challenges

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[101][101];

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