Given two numbers N and Okay, the duty is to depend the variety of all doable arrays of dimension N such that every component is a optimistic integer lower than or equal to Okay and is both a a number of or a divisor of its neighbours. For the reason that reply will be massive, print it modulo 109 + 7.

Examples: 

Enter: N = 2, Okay = 3
Output: 7
Rationalization: All of the doable arrays are – { {1, 2}, {2, 1}, {1, 3}, {3, 1}, {1, 1}, {2, 2}, {3, 3} }

Enter: N = 5, Okay = 4
Output: 380

 

Naive Strategy: The best strategy is to search out all mixtures of arrays of dimension N the place every component is lower than or equal to ‘Okay’, and for every mixture verify if adjoining parts are multiples of one another or not. 

Time Complexity: O(OkayN * N)
Auxiliary Area: O(N)

Environment friendly Strategy: The above strategy can be optimized through the use of Dynamic Programming due to its overlapping subproblems and optimum substructure property utilizing the next remark: 

The subproblems will be saved in dp[][] desk utilizing memoization the place dp[i][prev] shops the depend of all doable arrays from the ith place until the tip, with prev as the worth in (i-t)th index. 

Comply with the steps under to unravel the issue:

  • Initialize a worldwide multidimensional array dp[][] to retailer the results of every recursive name.
  • Discover the multiples and divisors of all numbers from 1 to Okay and retailer them.
  • Outline a recursive perform and carry out the next operations:
    • If the worth of i is N, return 1 as a sound array has been fashioned.
    • If the results of the state dp[i][prev] is already computed, return that calculated worth.
    • Iterate by means of all of the multiples and divisors of ‘prev‘, and for every quantity name the recursive perform for (i + 1)th index.
  • The worth at dp[0][1] would be the required reply.

Under is the implementation of the above strategy : 

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int dp[1005][1005];

  

vector<vector<int> > data(1005);

  

int countOfArrays(int index, int prev, int N)

{

    

    

    if (index == N) {

        return 1;

    }

  

    

    if (dp[index][prev] != -1) {

        return dp[index][prev];

    }

    dp[index][prev] = 0;

  

    

    

    for (auto num : data[prev]) {

  

        

        

        dp[index][prev]

            += countOfArrays(index + 1,

                             num, N);

  

        

        dp[index][prev] %= 1000000007;

    }

  

    

    return dp[index][prev];

}

  

int UtilCountOfArrays(int N, int Okay)

{

  

    

    memset(dp, -1, sizeof dp);

  

    

    

    for (int i = 1; i <= Okay; ++i) {

        for (int j = 1; j <= Okay; ++j) {

            if (i % j == 0 or j % i == 0) {

                data[i].push_back(j);

            }

        }

    }

  

    

    return countOfArrays(0, 1, N);

}

  

int principal()

{

    

    int N = 2;

    int Okay = 3;

    cout << UtilCountOfArrays(N, Okay) << endl;

    return 0;

}

Time Complexity: O(N * Okay * √Okay)
Auxiliary Area: O(N * Okay)

By admin

Leave a Reply

Your email address will not be published.