Given N and K, the task is to form an array where each element represents the number of ways to reach each index i (1 ? i ? N) by taking only the steps where step length is divisible by incremented K i.e., first step length should be divisible by K. Next, step length should be divisible by K + 1 and so on.
Note: Step length is the difference between the values of the current index and the index at which we are going to reach.
Examples:
Input: N = 8, K = 1
Output: {1, 1, 2, 2, 3, 4, 5, 6 }
Explanation: Ways to reach point 1: [0, 1] –> (1-0) divisible by 1
Ways to reach point 2: [0, 2] —> (2 – 0) divisible by 2
Ways to reach point 3: [0, 1, 3], [0, 3] –> in the first way (1 – 0) divisible by K = 1, (3 – 1) divisible by K = 2, in the 2nd way (3 – 0) is divisible by 1 taking the first direct step as multiple of 1.
Ways to reach point 4: [0, 2, 4], [0, 4]
Ways to reach point 5: [0, 1, 5], [0, 3, 5], [0, 5]
Ways to reach point 6: [0, 1, 3, 6], [0, 2, 6], [0, 4, 6], [0, 6]
Ways to reach point 7: [0, 2, 4, 7], [0, 1, 7], [0, 3, 7], [0, 5, 7], [0, 7]
Ways to reach point 8: [0, 3, 5, 8], [0, 1, 5, 8], [0, 2, 8], [0, 4, 8], [0, 6, 8], [0, 8].Input: N = 10, K = 2
Output: {0, 1, 0, 1, 1, 1, 1, 2, 2, 2 }
Approach: Implement the idea below to solve the problem:
The approach is based on the DP where we maintain three DP arrays dp1, dp2, res where dp1[i] stores the number of ways of reaching i by taking upto (K – 1) the multiple steps which is the previous number of ways to reach the ith step. dp2[i] represents the number of ways of reaching i by taking up to kth multiple steps and the res[i] array stores the sum of dp2[i] at each K.
Follow these steps to solve the above problem:
- Initialize min_d which is the position of starting at each step which is at a K.
- Initialize the dp1, dp2, and res.
- Assign dp1[0] = 1 as a base case i.e., the only way to reach 0.
- Initialize min_d = K.
- Iterate from i = K while min_d ? N i.e., the step length should not cross n.
- Fill the dp2 array using the relation dp2[j] = dp2[j – i] + dp1[j – i];
- Assign dp1 as dp2 which will be used in the next iteration
- Make all the elements of dp2 to 0 to be used in the next iteration
- Move min_d to the minimum possible next starting point from where the step can be started for the next K + 1.
- Print the res[] array.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of ways to// reach the destination i such that each// step should be divisible by k and next// step divisible k + 1void findNumways(int n, int k){ // Initialize min_d which is the // position of start at each step which // is at a k int min_d; vector<int> dp1(n + 1), dp2(n + 1), res(n + 1); // dp1[0] = 1 as a base case dp1[0] = 1; // Initialize min_d = k min_d = k; // Iterate from i =k while min_d <= n i.e // the step length should not cross n for (int i = k; min_d <= n; i++) { // Fill the dp2 array for (int j = min_d; j <= n; j++) { dp2[j] = dp2[j - i] + dp1[j - i]; res[j] = res[j] + dp2[j]; } // Assign dp1 as dp2 which would be // used in the next iteartion dp1 = dp2; // Make all the elements of dp2 to // 0 to be used in next iteration for (int j = 0; j <= n; j++) { dp2[j] = 0; } // Move min_d to the minimum // possible next starting point // from where the step can be // started for next k + 1. min_d = min_d + i + 1; } // Print the res[] array. for (int i = 1; i <= n; i++) { cout << res[i] << " "; }}// Driver functionint main(){ int N = 8, K = 1; // Function call findNumways(N, K); return 0;} |
Java
// Java code for the above approachimport java.util.*;public class Main {// Function to find the number of ways to// reach the destination i such that each// step should be divisible by k and next// step divisible k + 1static void findNumWays(int n, int k) {// Initialize min_d which is the// position of start at each step which// is at a kint min_d = k;int[] dp1 = new int[n + 1];int[] dp2 = new int[n + 1];int[] res = new int[n + 1]; // dp1[0] = 1 as a base casedp1[0] = 1;// Iterate from i =k while min_d <= n i.e// the step length should not cross nfor (int i = k; i <= n; i++) { for (int j = min_d; j <= n; j++) { dp2[j] = dp2[j - i] + dp1[j - i]; res[j] = res[j] + dp2[j]; } dp1 = dp2; dp2 = new int[n + 1]; min_d = min_d + i + 1;}// Print the res[] array.System.out.println(Arrays.toString(Arrays.copyOfRange(res, 1, res.length)));}// Driver functionpublic static void main(String[] args) {int N = 8;int K = 1; // Function callfindNumWays(N, K);}}//This code is contributed by shivamsharma215 |
Python3
# Function to find the number of ways to# reach the destination i such that each# step should be divisible by k and next# step divisible k + 1def findNumWays(n: int, k: int): # Initialize min_d which is the # position of start at each step which # is at a k min_d = k dp1 = [0] * (n + 1) dp2 = [0] * (n + 1) res = [0] * (n + 1) # dp1[0] = 1 as a base case dp1[0] = 1 # Iterate from i =k while min_d <= n i.e # the step length should not cross n for i in range(k, n + 1, 1): for j in range(min_d, n + 1): dp2[j] = dp2[j - i] + dp1[j - i] res[j] = res[j] + dp2[j] dp1 = dp2 dp2 = [0] * (n + 1) min_d = min_d + i + 1 # Print the res[] array. print(res[1:])# Driver functionif __name__ == "__main__": N = 8 K = 1 # Function call findNumWays(N, K)#This code is contributed by ik_9 |
C#
// C# code for the above approachusing System;public class GFG { // Function to find the number of ways to reach the // destination i such that each step should be divisible // by k and next step divisible k + 1 static void FindNumWays(int n, int k) { // Initialize min_d which is the position of start // at each step which is at a k int min_d = k; int[] dp1 = new int[n + 1]; int[] dp2 = new int[n + 1]; int[] res = new int[n + 1]; // dp1[0] = 1 as a base case dp1[0] = 1; // Iterate from i =k while min_d <= n i.e the step // length should not cross n for (int i = k; i <= n; i++) { for (int j = min_d; j <= n; j++) { dp2[j] = dp2[j - i] + dp1[j - i]; res[j] = res[j] + dp2[j]; } dp1 = dp2; dp2 = new int[n + 1]; min_d = min_d + i + 1; } // Print the res[] array. for (int i = 1; i <= n; i++) { Console.Write(res[i] + " "); } } static public void Main() { // Code int N = 8; int K = 1; // Function call FindNumWays(N, K); }}// This code is contributed by karthik |
Javascript
// Function to find the number of ways to// reach the destination i such that each// step should be divisible by k and next// step divisible k + 1function findNumways(n, k) { // Initialize min_d which is the // position of start at each step which // is at a k let min_d; let dp1 = Array(n + 1).fill(0); let dp2 = Array(n + 1).fill(0); let res = Array(n + 1).fill(0); // dp1[0] = 1 as a base case dp1[0] = 1; // Initialize min_d = k min_d = k; // Iterate from i =k while min_d <= n i.e // the step length should not cross n for (let i = k; min_d <= n; i++) { // Fill the dp2 array for (let j = min_d; j <= n; j++) { dp2[j] = dp2[j - i] + dp1[j - i]; res[j] = res[j] + dp2[j]; } // Assign dp1 as dp2 which would be // used in the next iteartion dp1 = dp2.slice(); // Make all the elements of dp2 to // 0 to be used in next iteration for (let j = 0; j <= n; j++) { dp2[j] = 0; } // Move min_d to the minimum // possible next starting point // from where the step can be // started for next k + 1. min_d = min_d + i + 1; } // Print the res[] array. for (let i = 1; i <= n; i++) { console.log(res[i] + " "); }}// Driver functionfunction main() { let N = 8, K = 1; // Function call findNumways(N, K);}main();//code by ksam24000 |
1 1 2 2 3 4 5 6
Time Complexity: O(N * K)
Auxiliary Space: O(N)
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
