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 approachÂ
using 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 |
Output
1 1 2 2 3 4 5 6
Time Complexity: O(N * K)Â
Auxiliary Space: O(N)
Related Articles:
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!
