Count ways to reach each index by taking steps that is multiple of incremented K

0 0 7 minutes read

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 i^th 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 + 1
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;
 
    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 function
int main()
{
 
    int N = 8, K = 1;
 
    // Function call
    findNumways(N, K);
    return 0;
}

Java

// Java code for the above approach
import 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 + 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.
System.out.println(Arrays.toString(Arrays.copyOfRange(res, 1, res.length)));
}
 
// Driver function
public static void main(String[] args) {
int N = 8;
int K = 1;
  // Function call
findNumWays(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 + 1
def 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 function
if __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 + 1
function 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 function
function 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:

Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials

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 zambiatek!