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 k elements that are still not used. Now at each index i, calculate(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 k 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 P 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";
}
}
You can also try this code with Online C++ Compiler
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";
}
}
You can also try this code with Online C++ Compiler
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!
244+ registered 
