Number of ways to cut a stick of length N into in even length at most K units long pieces
Given a rod of length N units, the task is to find the number of ways to cut the rod into parts such that the length of each part is even and each part is at most K units.
Examples:
Input: N = 6, K = 4
Output: 3
Explanation:
Rod of length 6 units needs to be into parts having length at most 4 units. Hence cut the rod in three ways:
Way 1: 2 units + 2 units + 2 units
Way 2: 2 units + 4 units
Way 3: 4 units + 2 unitsInput: N = 4, K = 2
Output: 1
Explanation:
Rod of length 4 units needs to be into parts having length at most 2 units. Hence cut the rod in 2 + 2 units.
Approach: The idea is to use dynamic programming where the optimal sub-structure is that the length of each part should be even. Count all the way to cut the rod by calling the function recursively for a piece obtained after a cut.
Below is the implementation of the above approach:
C++14
// C++14 program for the above approach#include <bits/stdc++.h>using namespace std;// Recursive Function to count// the total number of waysint solve(int n, int k, int mod, int dp[]){ // Base case if no-solution exist if (n < 0) return 0; // Condition if a solution exist if (n == 0) return 1; // Check if already calculated if (dp[n] != -1) return dp[n]; // Initialize counter int cnt = 0; for (int i = 2; i <= k; i += 2) { // Recursive call cnt = (cnt % mod + solve(n - i, k, mod, dp) % mod) % mod; } // Store the answer dp[n] = cnt; // Return the answer return cnt;}// Driver codeint main(){ const int mod = 1e9 + 7; int n = 4, k = 2; int dp[n + 1]; memset(dp, -1, sizeof(dp)); int ans = solve(n, k, mod, dp); cout << ans << '\n'; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Recursive Function to count// the total number of waysstatic int solve(int n, int k, int mod, int dp[]){ // Base case if no-solution exist if (n < 0) return 0; // Condition if a solution exist if (n == 0) return 1; // Check if already calculated if (dp[n] != -1) return dp[n]; // Initialize counter int cnt = 0; for(int i = 2; i <= k; i += 2) { // Recursive call cnt = (cnt % mod + solve(n - i, k, mod, dp) % mod) % mod; } // Store the answer dp[n] = cnt; // Return the answer return cnt;}// Driver codepublic static void main(String[] args){ int mod = (int)(1e9 + 7); int n = 4, k = 2; int []dp = new int[n + 1]; for(int i = 0; i < n + 1; i++) dp[i] = -1; int ans = solve(n, k, mod, dp); System.out.println(ans);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Recursive function to count# the total number of waysdef solve(n, k, mod, dp): # Base case if no-solution exist if (n < 0): return 0 # Condition if a solution exist if (n == 0): return 1 # Check if already calculated if (dp[n] != -1): return dp[n] # Initialize counter cnt = 0 for i in range(2, k + 1, 2): # Recursive call cnt = ((cnt % mod + solve(n - i, k, mod, dp) % mod) % mod) # Store the answer dp[n] = cnt # Return the answer return int(cnt)# Driver codeif __name__ == '__main__': mod = 1e9 + 7 n = 4 k = 2 dp = [-1] * (n + 1) ans = solve(n, k, mod, dp) print(ans) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Recursive function to count// the total number of waysstatic int solve(int n, int k, int mod, int []dp){ // Base case if no-solution exist if (n < 0) return 0; // Condition if a solution exist if (n == 0) return 1; // Check if already calculated if (dp[n] != -1) return dp[n]; // Initialize counter int cnt = 0; for(int i = 2; i <= k; i += 2) { // Recursive call cnt = (cnt % mod + solve(n - i, k, mod, dp) % mod) % mod; } // Store the answer dp[n] = cnt; // Return the answer return cnt;}// Driver codepublic static void Main(String[] args){ int mod = (int)(1e9 + 7); int n = 4, k = 2; int []dp = new int[n + 1]; for(int i = 0; i < n + 1; i++) dp[i] = -1; int ans = solve(n, k, mod, dp); Console.WriteLine(ans);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to implement// the above approach// Recursive Function to count// the total number of waysfunction solve(n, k, mod, dp){ // Base case if no-solution exist if (n < 0) return 0; // Condition if a solution exist if (n == 0) return 1; // Check if already calculated if (dp[n] != -1) return dp[n]; // Initialize counter let cnt = 0; for(let i = 2; i <= k; i += 2) { // Recursive call cnt = (cnt % mod + solve(n - i, k, mod, dp) % mod) % mod; } // Store the answer dp[n] = cnt; // Return the answer return cnt;} // Driver Code let mod = (1e9 + 7); let n = 4, k = 2; let dp = new Array(n+1).fill(0); for(let i = 0; i < n + 1; i++) dp[i] = -1; let ans = solve(n, k, mod, dp); document.write(ans); </script> |
Output
1
Time complexity: O(n*k)
Auxiliary Space: O(n)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a array DP of size n+1 to store the solution of the subproblems and initialize it with 0.
- Initialize the table with base cases dp[0] = 1.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Return the final solution stored in dp[n].
Implementation :
C++
// C++ program for the above approach using DP tabulation#include <bits/stdc++.h>using namespace std;// Function to count the total number of waysint countWays(int n, int k, int mod){ // Create a DP table int dp[n + 1]; memset(dp, 0, sizeof(dp)); // Initialize DP table dp[0] = 1; // Fill the DP table for (int i = 1; i <= n; i++) { for (int j = 2; j <= k; j += 2) { if (i - j >= 0) { dp[i] = (dp[i] + dp[i - j]) % mod; } } } // Return the answer return dp[n];}// Driver Codeint main(){ const int mod = 1e9 + 7; int n = 4, k = 2; int ans = countWays(n, k, mod); cout << ans << '\n'; return 0;}// this code is contributed by bhardwajji |
Java
// Java program for the above approach using DP tabulationimport java.util.*;class Main { // Function to count the total number of ways static int countWays(int n, int k, int mod) { // Create a DP table int[] dp = new int[n + 1]; Arrays.fill(dp, 0); // Initialize DP table dp[0] = 1; // Fill the DP table for (int i = 1; i <= n; i++) { for (int j = 2; j <= k; j += 2) { if (i - j >= 0) { dp[i] = (dp[i] + dp[i - j]) % mod; } } } // Return the answer return dp[n]; } // Driver Code public static void main(String[] args) { final int mod = 1000000007; int n = 4, k = 2; int ans = countWays(n, k, mod); System.out.println(ans); }} |
C#
using System;public class MainClass { // Function to count total number of ways static int CountWays(int n, int k, int mod) { // Create a DP table int[] dp = new int[n + 1]; Array.Fill(dp, 0); // Initialize DP table dp[0] = 1; // Fill the DP table for (int i = 1; i <= n; i++) { for (int j = 2; j <= k; j += 2) { if (i - j >= 0) { dp[i] = (dp[i] + dp[i - j]) % mod; } } } // Return the answer return dp[n]; } // Driver Code public static void Main() { const int mod = 1000000007; int n = 4, k = 2; int ans = CountWays(n, k, mod); Console.WriteLine(ans); }} |
Python3
def countWays(n, k, mod): # Create a DP table dp = [0] * (n+1)# Initialize DP table dp[0] = 1# Fill the DP table for i in range(1, n+1): for j in range(2, k+1, 2): if i - j >= 0: dp[i] = (dp[i] + dp[i-j]) % mod# Return the answer return dp[n]mod = int(1e9 + 7)n, k = 4, 2ans = countWays(n, k, mod)print(ans) |
Output
1
Time complexity: O(n*k)
Auxiliary Space: O(n)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
