Given two integers N and K, find the distinct number of ways to create an array of N elements where each element is in the range [1, K] and every pair of adjacent elements (P, Q) is such that either P <= Q or P % Q > 0.
Example:
Input: N = 2, K = 3
Output: 7
Explanation: The arrays that satisfies the given conditions are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}, {3, 2}.Input: N = 9, K = 1
Output: 1
Explanation: : The only arrays that satisfies the given conditions is {1, 1, 1, 1, 1, 1, 1, 1, 1}.
Approach: The given problem can be solved using Dynamic Programming based on the following observations:
- Consider a 2D array, say dp[][] where dp[x][y] represents the count of arrays of length x having y as their last element.
- Now, the number of ways to create an array of length x having y as their last element and having all array elements in the range [1, K] is the sum of ways to create an array of length (y – 1) having the last element over the range [1, K] and can be represented as relation .
- The only cases where P <= Q or P % Q > 0 are to be considered where (P, Q) are the pair of adjacent elements. The array that do not satisfy either of these conditions can be subtracted from each state using the relation are where y % j = 0.
From the above observations, compute the dp[][] table and print the value of dp[N][K] as the resultant count of arrays formed. Follow the steps below to solve the given problem:
- Store all the divisors of all the integers over the range [1, K] using the approach in Sieve of Eratosthenes in an array say divisor[][].
- Initialize a 2D array, say dp[][] of dimension (N + 1)*(K + 1) such that dp[x][y] represents the count of arrays of length x having y as their last element.
- Initialize a dp[1][j] to 1 as the number of ways to create an array of size 1 having any element j as their last element is 1.
- Iterate over the range [2, N] using the variable x and perform the following steps:
- For each possible values of j over the range [1, K] increment the value of dp[x][y] by dp[x – 1][j].
- Iterate over the range [1, K] using the value of y and for each divisor, say D of y decrement the value of dp[x][y] by dp[x – 1][D] as this doesn’t satisfy cases where P <= Q or P % Q > 0 for all pair of adjacent elements (P, Q).
- After completing the above steps, print the value of as the result.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of distinct // arrays of size n having elements in // range [1, k] and all adjacent elements // (P, Q) follows (P <= Q) or (P % Q > 0) int countArrays( int n, int k) { // Stores the divisors of all // integers in the range [1, k] vector<vector< int > > divisors(k + 1); // Calculate the divisors of all // integers using the Sieve for ( int i = 1; i <= k; i++) { for ( int j = 2 * i; j <= k; j += i) { divisors[j].push_back(i); } } // Stores the dp states such that // dp[i][j] with i elements having // j as the last element of array vector<vector< int > > dp( n + 1, vector< int >(k + 1)); // Initialize the dp array for ( int j = 1; j <= k; j++) { dp[1][j] = 1; } // Calculate the dp states using the // derived relation for ( int x = 2; x <= n; x++) { // Calculate the sum for len-1 int sum = 0; for ( int j = 1; j <= k; j++) { sum += dp[x - 1][j]; } // Subtract dp[len-1][j] for each // factor of j from [1, K] for ( int y = 1; y <= k; y++) { dp[x][y] = sum; for ( int d : divisors[y]) { dp[x][y] = (dp[x][y] - dp[x - 1][d]); } } } // Calculate the final result int sum = 0; for ( int j = 1; j <= k; j++) { sum += dp[n][j]; } // Return the resultant sum return sum; } // Driver Code int main() { int N = 2, K = 3; cout << countArrays(N, K); return 0; } |
Java
// Java program of the above approach import java.util.*; class GFG{ // Function to find the count of distinct // arrays of size n having elements in // range [1, k] and all adjacent elements // (P, Q) follows (P <= Q) or (P % Q > 0) static int countArrays( int n, int k) { // Stores the divisors of all // integers in the range [1, k] Vector<Integer> []divisors = new Vector[k + 1 ]; for ( int i = 0 ; i < divisors.length; i++) divisors[i] = new Vector<Integer>(); // Calculate the divisors of all // integers using the Sieve for ( int i = 1 ; i <= k; i++) { for ( int j = 2 * i; j <= k; j += i) { divisors[j].add(i); } } // Stores the dp states such that // dp[i][j] with i elements having // j as the last element of array int [][] dp = new int [n + 1 ][k + 1 ]; // Initialize the dp array for ( int j = 1 ; j <= k; j++) { dp[ 1 ][j] = 1 ; } // Calculate the dp states using the // derived relation for ( int x = 2 ; x <= n; x++) { // Calculate the sum for len-1 int sum = 0 ; for ( int j = 1 ; j <= k; j++) { sum += dp[x - 1 ][j]; } // Subtract dp[len-1][j] for each // factor of j from [1, K] for ( int y = 1 ; y <= k; y++) { dp[x][y] = sum; for ( int d : divisors[y]) { dp[x][y] = (dp[x][y] - dp[x - 1 ][d]); } } } // Calculate the final result int sum = 0 ; for ( int j = 1 ; j <= k; j++) { sum += dp[n][j]; } // Return the resultant sum return sum; } // Driver Code public static void main(String[] args) { int N = 2 , K = 3 ; System.out.print(countArrays(N, K)); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program of the above approach # Function to find the count of distinct # arrays of size n having elements in # range [1, k] and all adjacent elements # (P, Q) follows (P <= Q) or (P % Q > 0) def countArrays(n, k): # Stores the divisors of all # integers in the range [1, k] divisors = [[] for i in range (k + 1 )] # Calculate the divisors of all # integers using the Sieve for i in range ( 1 , k + 1 , 1 ): for j in range ( 2 * i, k + 1 , i): divisors[j].append(i) # Stores the dp states such that # dp[i][j] with i elements having # j as the last element of array dp = [[ 0 for i in range (k + 1 )] for j in range (n + 1 )] # Initialize the dp array for j in range ( 1 , k + 1 , 1 ): dp[ 1 ][j] = 1 # Calculate the dp states using the # derived relation for x in range ( 2 , n + 1 , 1 ): # Calculate the sum for len-1 sum = 0 for j in range ( 1 , k + 1 , 1 ): sum + = dp[x - 1 ][j] # Subtract dp[len-1][j] for each # factor of j from [1, K] for y in range ( 1 , k + 1 , 1 ): dp[x][y] = sum for d in divisors[y]: dp[x][y] = (dp[x][y] - dp[x - 1 ][d]) # Calculate the final result sum = 0 for j in range ( 1 , k + 1 , 1 ): sum + = dp[n][j] # Return the resultant sum return sum # Driver Code if __name__ = = '__main__' : N = 2 K = 3 print (countArrays(N, K)) # This code is contributed by ipg2016107. |
C#
// C# program for the approach using System; using System.Collections.Generic; class GFG { // Function to find the count of distinct // arrays of size n having elements in // range [1, k] and all adjacent elements // (P, Q) follows (P <= Q) or (P % Q > 0) static int countArrays( int n, int k) { // Stores the divisors of all // integers in the range [1, k] List< int > []divisors = new List< int >[k + 1]; for ( int i = 0; i < divisors.Length; i++) divisors[i] = new List< int >(); // Calculate the divisors of all // integers using the Sieve for ( int i = 1; i <= k; i++) { for ( int j = 2 * i; j <= k; j += i) { divisors[j].Add(i); } } // Stores the dp states such that // dp[i][j] with i elements having // j as the last element of array int [,] dp = new int [n + 1, k + 1]; // Initialize the dp array for ( int j = 1; j <= k; j++) { dp[1, j] = 1; } int sum; // Calculate the dp states using the // derived relation for ( int x = 2; x <= n; x++) { // Calculate the sum for len-1 sum = 0; for ( int j = 1; j <= k; j++) { sum += dp[x - 1, j]; } // Subtract dp[len-1][j] for each // factor of j from [1, K] for ( int y = 1; y <= k; y++) { dp[x, y] = sum; foreach ( int d in divisors[y]) { dp[x, y] = (dp[x, y] - dp[x - 1, d]); } } } // Calculate the final result sum = 0; for ( int j = 1; j <= k; j++) { sum += dp[n, j]; } // Return the resultant sum return sum; } // Driver Code public static void Main() { int N = 2, K = 3; Console.Write(countArrays(N, K)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the count of distinct // arrays of size n having elements in // range [1, k] and all adjacent elements // (P, Q) follows (P <= Q) or (P % Q > 0) function countArrays(n, k) { // Stores the divisors of all // integers in the range [1, k] let divisors = new Array(k + 1).fill( new Array()); // Calculate the divisors of all // integers using the Sieve for (let i = 1; i <= k; i++) { for (let j = 2 * i; j <= k; j += i) { divisors[j].push(i); } } // Stores the dp states such that // dp[i][j] with i elements having // j as the last element of array let dp = new Array(n + 1).fill( new Array(k + 1)); // Initialize the dp array for (let j = 1; j <= k; j++) { dp[1][j] = 1; } // Calculate the dp states using the // derived relation for (let x = 2; x <= n; x++) { // Calculate the sum for len-1 let sum = 0; for (let j = 1; j <= k; j++) { sum += dp[x - 1][j]; } // Subtract dp[len-1][j] for each // factor of j from [1, K] for (let y = 1; y <= k; y++) { dp[x][y] = sum; for (let d of divisors[y]) { dp[x][y] = (dp[x][y] - dp[x - 1][d]); } } } // Calculate the final result let sum = 0; for (let j = 1; j <= k; j++) { sum += dp[n][j]; } sum++; // Return the resultant sum return sum; } // Driver Code let N = 2, K = 3; document.write(countArrays(N, K)); // This code is contributed by Potta Lokesh </script> |
7
Time Complexity: O(N*K*log K)
Auxiliary Space: O(K*log K)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!