Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Understanding
2.
Problem Statement
2.1.
Input 1
2.2.
Output 1
2.3.
Explanation
2.4.
Input 2
2.5.
Output 2
2.6.
Explanation
3.
Approach 1
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Approach 2
4.1.
Program
4.2.
Input
4.3.
Output
4.4.
Time Complexity
4.5.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Count of valid arrays of size P with elements in the range [1, N] having duplicates at least M distance apart

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Understanding

In this blog, we will discuss a problem based on dynamic programming. Dynamic programming is a widely asked topic in coding contests and technical interviews. Dynamic programming is primarily an optimized recursion. We use Dynamic Programming to optimize any recursive solution that involves repeated calls for the same inputs. We will be using recursion with memoization to solve this problem.

Problem Statement

Ninja has given you three integers, ‘N’, ‘M’, and ‘P’. Your task is to find the number of valid arrays made of given size ‘P’ having each integer between [1, N], such that the duplicates appear at least ‘M’ distance apart.

 

Input Format

The number of test cases ‘T’ in the first line.

Then T lines follow, each having three integers ‘N’, ‘M’, and ‘P’.

 

T

N1 M1 P1

Nn Mn Pn

 

Output Format

Output the total number of valid arrays that can be formed.

Input 1

N = 2, M = 0, and P = 3

Output 1

6

Explanation

Arrays that can be formed are: {1, 2, 1}, {1, 1, 2}, {2, 1, 1}, {2, 2, 1}, {2, 1, 2}, {1, 2, 2}.

Input 2

N = 2, M = 1, and P = 4

Output 2

2

Explanation

Arrays that can be formed are: {1, 2, 1, 2}, {2, 1, 2, 1}.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1

Here we can observe that while building the array, we have two choices at any index. Either we use an already used element that is at least ‘M’ distance apart, or we can use an element that has not been used till now. Using this observation, we can formulate a recursive solution. First, let us decide the states. We want the number of possible arrays that can be created which follow the given conditions. So let calculate(i, j, k) be the number of possible arrays till i’th position where j unique elements are already being used, and there are elements that are still not used. Now at each index icalculate(i + 1, j, k) denotes that we chose an already used element that is at least ‘M’ distance apart. And calculate(i + 1, j + 1, k - 1) denotes that we chose an unused element. 

During building the valid arrays at every index we have these choices therefore:

calculate(i, j, k) = (j - M) * calculate(i + 1,  j,  k) * calculate(i + 1, j + 1, k - 1) 
 

When choosing an already used element, we need to multiply it with (j - M) because we are picking an element that is already used and is at least ‘M’ distance apart (so there are j - M choices). Similarly, when selecting an unused element, we had choices, so we multiplied it with k.

Algorithm

1. Write a recursive function to calculate the count of valid arrays.

2. Base Case: Check if all places have been filled. After filling all P, if no unused element is left, return 1. Otherwise, return 0.

3. Calculate the answer for the current state (using the recursive relation).

4. Store and return the answer for the current state.

Program

#include <iostream>
#include <cstring>
using namespace std;

#define MAXSIZE 101


int N, M, P;

// Function for calculating the dp states.
int calculate(int position, int used, int unused){

    // BASE CASE
    if(position == P){
        /* If the size of array has become P
        and there are no unused elements left.
        Then return 1. */
        return unused == 0;
    }

    /* To store the final answer. */
    int ways = 0;

    /* CASE 1 : Using an unused number. */
    if(unused > 0){
        /* Since we can choose from ‘UNUSED’ number of elements,
        we will multiply the answer from 'unused' */
        ways += calculate(position+1, used+1, unused-1) * unused;
    }

    /* CASE 2 : Using already used number which at least ‘M’
    distance back. */
    if(used > M){
        /* Since we need an element which is used and
        also is at least M distance away, we will have 'USED - M' choices. */
        ways += calculate(position + 1, used, unused) * (used - M);
    }
   
    // Store and return the answer for this state.
    return ways;
}

// Driver Code.
int main(){
    int tt = 1;
    cin >> tt;
    while(tt--){  
        cin >> N >> M >> P;

        cout << "For N = " << N << ", M = " << M << ", P = " << P << ",\n";
        cout << "Number of valid arrays are: " << calculate(0, 0, N) << "\n\n";
    }
}

 

Input

2
2 0 3
2 1 4

Output

For N = 2, M = 0, P = 3,
The number of valid arrays are: 6

For N = 2, M = 1, P = 4,
The number of valid arrays are: 2

Time Complexity

The time complexity of above recursive approach is O(2 ^ (N * M * P) ), where ‘N’, ‘M’ and ‘P’ are given input parameters.

It is because there a total of N * M * P states.

Space Complexity

The space complexity of the above approach is O(N+M+P), because stack size can grow maximum to N+M+P.

Approach 2

Since the time complexity of the above approach is exponential, it is very inefficient. So we memoize the above solution to reduce time complexity from exponential to polynomial time.

Program

#include <iostream>
#include <cstring>
using namespace std;

#define MAXSIZE 101

int dp[MAXSIZE][MAXSIZE][MAXSIZE];

int N, M, P;

// Function for calculating the dp states.
int calculateDP(int position, int used, int unused){

    // BASE CASE
    if(position == P){
        /* If the size of array has become P
        and there are no unused elements left.
        Then return 1. */
        return unused == 0;
    }

    /* Check if this state exist in DP table */
    if(dp[position][used][unused] != -1){
        return dp[position][used][unused];
    }

    /* To store the final answer. */
    int ways = 0;

    /* CASE 1 : Using an unused number. */
    if(unused > 0){
        /* Since we can choose from 'unused' number of elements,
        we will multiply the answer from 'unused' */
        ways += calculateDP(position+1, used+1, unused-1) * unused;
    }

    /* CASE 2 : Using already used number which at least M
    distance back. */
    if(used > M){
        /* Since we need an element which is used and
        also is at least M distance away, we will have 'used-M' choices. */
        ways += calculateDP(position+1, used, unused) * (used-M);
    }
   
    // Store and return the answer for this state.
    return dp[position][used][unused] = ways;
}

// Driver Code.
int main(){
    int tt = 1;
    cin >> tt;
    while(tt--){  
        cin >> N >> M >> P;

        /* Initialize dp table with -1 */
        memset(dp, -1, sizeof(dp));

        cout << "For N = " << N << ", M = " << M << ", P = " << P << ",\n";
        cout << "Number of valid arrays are: " << calculateDP(0, 0, N) << "\n\n";
    }
}

Input

2
2 0 3
2 1 4

Output

For N = 2, M = 0, P = 3,
The number of valid arrays are: 6

For N = 2, M = 1, P = 4,
The number of valid arrays are: 2

Time Complexity

The time complexity of the above approach is O(N * M * P), where ‘N’, ‘M’, and ‘P’ are input parameters.

It is because for the code to complete, it must fill all the positions in the ‘DP’ array. As the size of ‘DP’ array is N * M * P and it takes O(1) time to check and fill each position with no repetition, the time complexity becomes O(N * M * P).

Space Complexity

The auxiliary space complexity of the above approach is O(N * M * P), where ‘N’, ‘M’, and ‘P’ are input parameters.

 It is because we have declared a 3-dimensional array of this much size.

Check out Longest Common Substring

Key Takeaways

We used a dynamic approach in this blog to solve the problem. Using memoization, we improved the time complexity of the solution from exponential to polynomial. Questions involving strings are prevalent in interviews. Such questions are generally easier to implement but require keen observation for designing proper solutions.

Hence learning never stops, and there is a lot more to learn.

Check out this problem - Frog Jump

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Previous article
Maximum sum subsequence of any size which is decreasing-increasing alternatively
Next article
Check if a path exists from start to end cell in given Matrix with obstacles in at most K moves
Live masterclass