Go to CDN’s CopyGiven three integers N, M and P, the task is to find the total number of valid arrays that can be created of size P having each element in range [1, N], such that the duplicates appear at least M distance apart.
Example:
Input: N = 2, M = 0, P = 3
Output: 6
Explanation: All valid arrays are: {1, 2, 1}, {1, 1, 2}, {2, 1, 1}, {2, 2, 1}, {2, 1, 2}, {1, 2, 2}.Input: N = 2, M = 1, P = 4
Output: 2
Explanation: All valid arrays are: {1, 2, 1, 2}, {2, 1, 2, 1}
Approach: The problem can be solved with the help of Dynamic Programming,
- There are two choices possible at each index are : either we append already used element at least M distance apart, or we append a new element and decrement the count of unused characters.
- To handle this, use recursive dynamic programming.
- To speed up the recursive calls, use memoization so that already calculated states are not calculated again.
- Let’s define: dp[i][j][k] as the number of arrays till i-th position in which j unique elements are present and k be number of elements which are not used.
- At each step there are two options:
1. Choose previously occurred elements, j and k wouldn’t change as number of used and unused elements doesn’t change : dp[i+1][j][k]
2. Choose element that has never been used, for this case, the number of used character will increment by 1 and the number of unused characters will decrement by 1 : dp[i+1][j+1][k-1]
dp[i][j][k] will be the summation of above two steps, represented as :
dp[i][j][k] = dp[i+1][j][k] + dp[i+1][j+1][k-1]
- The final answer will be dp[0][0][N].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the total // number of arrays int calculate(int position, int used, int unused, int P, int M, vector<vector<vector<int> > >& dp) { // If the size of the array is P if (position == P) { // Check if all elements are // used atleast once return unused == 0 ? 1 : 0; } // Check if this state is already // calculated if (dp[position][used][unused] != -1) return dp[position][used][unused]; // Initialize the result int result = 0; // Use a number from the list of // unused numbers if (unused > 0) { // There are 'unused' number of // favourable choices result += calculate(position + 1, used + 1, unused - 1, P, M, dp) * unused; } // Use a number from already present number // atleast M distance back if (used > M) { // There are 'used - M' number of // favourable choices result += calculate(position + 1, used, unused, P, M, dp) * (used - M); } // Store the result return dp[position][used][unused] = result; } // Function to solve the problem int solve(int N, int P, int M) { // Initialize DP table : dp[i][j][j] // i : current position/index // j : number of used elements // k : number of unused elements vector<vector<vector<int> > > dp( 101, vector<vector<int> >(101, vector<int>(101, -1))); return calculate(0, 0, N, P, M, dp); } // Driver Code int main() { int N = 2, M = 0, P = 3; cout << solve(N, P, M); } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to calculate the total // number of arrays static int calculate(int position, int used, int unused, int P, int M, int dp[][][]) { // If the size of the array is P if (position == P) { // Check if all elements are // used atleast once return unused == 0 ? 1 : 0; } // Check if this state is already // calculated if (dp[position][used][unused] != -1) return dp[position][used][unused]; // Initialize the result int result = 0; // Use a number from the list of // unused numbers if (unused > 0) { // There are 'unused' number of // favourable choices result += calculate(position + 1, used + 1, unused - 1, P, M, dp) * unused; } // Use a number from already present number // atleast M distance back if (used > M) { // There are 'used - M' number of // favourable choices result += calculate(position + 1, used, unused, P, M, dp) * (used - M); } // Store the result return dp[position][used][unused] = result; } // Function to solve the problem static int solve(int N, int P, int M) { // Initialize DP table : dp[i][j][j] // i : current position/index // j : number of used elements // k : number of unused elements int[][][] dp = new int[101][101][101]; for(int i = 0; i < 101; i++) { for(int j = 0; j < 101; j++) for(int k = 0; k < 101; k++) dp[i][j][k] = -1; } return calculate(0, 0, N, P, M, dp); } // Driver Code public static void main(String[] args) { int N = 2, M = 0, P = 3; System.out.println(solve(N, P, M)); } } // This code is contributed by dwivediyash |
Python3
# Python 3 program for the above approach # Function to calculate the total # number of arrays def calculate(position, used, unused, P, M, dp): # If the size of the array is P if (position == P): # Check if all elements are # used atleast once if unused == 0: return 1 else: return 0 # Check if this state is already # calculated if (dp[position][used][unused] != -1): return dp[position][used][unused] # Initialize the result result = 0 # Use a number from the list of # unused numbers if (unused > 0): # There are 'unused' number of # favourable choices result += calculate(position + 1, used + 1,unused - 1, P, M, dp)* unused # Use a number from already present number # atleast M distance back if (used > M): # There are 'used - M' number of # favourable choices result += calculate(position + 1,used, unused, P,M, dp)* (used - M) dp[position][used][unused] = result # Store the result return dp[position][used][unused] # Function to solve the problem def solve(N, P, M): # Initialize DP table : dp[i][j][j] # i : current position/index # j : number of used elements # k : number of unused elements dp = [[[-1 for i in range(101)] for i in range(101)] for j in range(101)] return calculate(0, 0, N, P, M, dp) # Driver Code if __name__ == '__main__': N = 2 M = 0 P = 3 print(solve(N, P, M)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; public class GFG { // Function to calculate the total // number of arrays static int calculate(int position, int used, int unused, int P, int M, int [,,]dp) { // If the size of the array is P if (position == P) { // Check if all elements are // used atleast once return unused == 0 ? 1 : 0; } // Check if this state is already // calculated if (dp[position,used,unused] != -1) return dp[position,used,unused]; // Initialize the result int result = 0; // Use a number from the list of // unused numbers if (unused > 0) { // There are 'unused' number of // favourable choices result += calculate(position + 1, used + 1, unused - 1, P, M, dp) * unused; } // Use a number from already present number // atleast M distance back if (used > M) { // There are 'used - M' number of // favourable choices result += calculate(position + 1, used, unused, P, M, dp) * (used - M); } // Store the result return dp[position,used,unused] = result; } // Function to solve the problem static int solve(int N, int P, int M) { // Initialize DP table : dp[i,j,j] // i : current position/index // j : number of used elements // k : number of unused elements int[,,] dp = new int[101,101,101]; for(int i = 0; i < 101; i++) { for(int j = 0; j < 101; j++) for(int k = 0; k < 101; k++) dp[i, j, k] = -1; } return calculate(0, 0, N, P, M, dp); } // Driver Code public static void Main(String[] args) { int N = 2, M = 0, P = 3; Console.WriteLine(solve(N, P, M)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to calculate the total // number of arrays function calculate(position, used, unused, P, M, dp) { // If the size of the array is P if (position == P) { // Check if all elements are // used atleast once return unused == 0 ? 1 : 0; } // Check if this state is already // calculated if (dp[position][used][unused] != -1) return dp[position][used][unused]; // Initialize the result let result = 0; // Use a number from the list of // unused numbers if (unused > 0) { // There are 'unused' number of // favourable choices result += calculate(position + 1, used + 1, unused - 1, P, M, dp) * unused; } // Use a number from already present number // atleast M distance back if (used > M) { // There are 'used - M' number of // favourable choices result += calculate(position + 1, used, unused, P, M, dp) * (used - M); } // Store the result return dp[position][used][unused] = result; } // Function to solve the problem function solve(N, P, M) { // Initialize DP table : dp[i][j][j] // i : current position/index // j : number of used elements // k : number of unused elements var dp = new Array(101); // create 2D for (let i = 0; i < dp.length; i++) { dp[i] = new Array(101).fill(-1); } // create 3D for (let i = 0; i < dp.length; i++) { for (let j = 0; j < dp[0].length; j++) { dp[i][j] = new Array(101).fill(-1); } } return calculate(0, 0, N, P, M, dp); } // Driver Code let N = 2, M = 0, P = 3; document.write(solve(N, P, M)); // This code is contributed by Potta Lokesh </script> |
Output
6
Time Complexity: O(N*M*P) (Because of three dependent variables)
Auxiliary Space: O(N*M*P) (Size of the DP matrix)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
