Given a K-ary tree, where each node is having K children and each edge has some weight. All the edges i.e. K, that goes from a particular node to all its children have weights in ascending order 1, 2, 3, …, K. Find the number of paths having total weight as W (sum of all edge weights in the path) starting from root and containing atleast one edge of weight atleast M.
Examples:
Input : W = 3, K = 3, M = 2 Output : 3 Explanation : One path can be (1 + 2), second can be (2 + 1) and third is 3.
Input : W = 4, K = 3, M = 2 Output : 6
Approach:
This problem can be solved using dynamic programming approach. The idea is to maintain two states, one for the current weight to be required and other one for a boolean variable which denotes that the current path has included an edge of weight atleast M or not. Iterate over all possible edge weights i.e. K and recursively solve for the weight W – i for 1 ≤ i ≤ K. If the current edge weight is more than or equal to M, set the boolean variable as 1 for the next call.
Below is the implementation of above approach.
C++
// C++ program to count the number of// paths with weight W in a K-ary tree#include <bits/stdc++.h>using namespace std;// Function to return the number of ways// having weight as wt in K-ary treeint solve(int dp[][2], int wt, int K, int M, int used){ // Return 0 if weight becomes less // than zero if (wt < 0) return 0; if (wt == 0) { // Return one only if the // current path has included // edge weight of atleast M if (used) return 1; return 0; } if (dp[wt][used] != -1) return dp[wt][used]; int ans = 0; for (int i = 1; i <= K; i++) { // If the current edge weight // is greater than or equal to // M, set used as true if (i >= M) ans += solve(dp, wt - i, K, M, used | 1); else ans += solve(dp, wt - i, K, M, used); } return dp[wt][used] = ans;}// Driver Code to test above functionint main(){ int W = 3, K = 3, M = 2; int dp[W + 1][2]; memset(dp, -1, sizeof(dp)); cout << solve(dp, W, K, M, 0) << endl; return 0;} |
Java
// Java program to count the number of // paths with weight W in a K-ary tree class GFG { // Function to return the number of ways // having weight as wt in K-ary tree public static int solve(int[][] dp, int wt, int K, int M, int used) { // Return 0 if weight becomes less // than zero if (wt < 0) { return 0; } if (wt == 0) { // Return one only if the // current path has included // edge weight of atleast M if (used == 1) { return 1; } return 0; } if (dp[wt][used] != -1) { return dp[wt][used]; } int ans = 0; for (int i = 1; i <= K; i++) { // If the current edge weight // is greater than or equal to // M, set used as true if (i >= M) { ans += solve(dp, wt - i, K, M, used | 1); } else { ans += solve(dp, wt - i, K, M, used); } } return dp[wt][used] = ans; } // Driver Code public static void main(String[] args) { int W = 3, K = 3, M = 2; int[][] dp = new int[W + 1][2]; for (int i = 0; i < W + 1; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = -1; } } System.out.print(solve(dp, W, K, M, 0) + "\n"); }}// This code has been contributed by 29AjayKumar |
Python3
# Python 3 program to count the number of # paths with weight W in a K-ary tree import numpy as np# Function to return the number of ways # having weight as wt in K-ary tree def solve(dp, wt, K, M, used) : # Return 0 if weight becomes less # than zero if (wt < 0) : return 0 if (wt == 0) : # Return one only if the # current path has included # edge weight of atleast M if (used) : return 1 return 0 if (dp[wt][used] != -1) : return dp[wt][used] ans = 0 for i in range(1, K + 1) : # If the current edge weight # is greater than or equal to # M, set used as true if (i >= M) : ans += solve(dp, wt - i, K, M, used | 1) else : ans += solve(dp, wt - i, K, M, used) dp[wt][used] = ans return ans# Driver Codeif __name__ == "__main__" : W = 3 K = 3 M = 2 dp = np.ones((W + 1, 2)); dp = -1 * dp print(solve(dp, W, K, M, 0)) # This code is contributed by Ryuga |
C#
// C# program to count the number of // paths with weight W in a K-ary tree using System; class GFG { // Function to return the number of ways // having weight as wt in K-ary tree public static int solve(int[,] dp, int wt, int K, int M, int used) { // Return 0 if weight becomes less // than zero if (wt < 0) return 0; if (wt == 0) { // Return one only if the // current path has included // edge weight of atleast M if (used == 1) return 1; return 0; } if (dp[wt,used] != -1) return dp[wt,used]; int ans = 0; for (int i = 1; i <= K; i++) { // If the current edge weight // is greater than or equal to // M, set used as true if (i >= M) ans += solve(dp, wt - i, K, M, used | 1); else ans += solve(dp, wt - i, K, M, used); } return dp[wt,used] = ans; } // Driver Code to test above function static void Main() { int W = 3, K = 3, M = 2; int[,] dp = new int[W + 1,2]; for(int i = 0;i < W + 1; i++) for(int j = 0; j < 2; j++) dp[i,j] = -1; Console.Write(solve(dp, W, K, M, 0) + "\n"); } //This code is contributed by DrRoot_} |
Javascript
<script> // Javascript program to count the number of // paths with weight W in a K-ary tree // Function to return the number of ways // having weight as wt in K-ary tree function solve(dp, wt, K, M, used) { // Return 0 if weight becomes less // than zero if (wt < 0) { return 0; } if (wt == 0) { // Return one only if the // current path has included // edge weight of atleast M if (used == 1) { return 1; } return 0; } if (dp[wt][used] != -1) { return dp[wt][used]; } let ans = 0; for (let i = 1; i <= K; i++) { // If the current edge weight // is greater than or equal to // M, set used as true if (i >= M) { ans += solve(dp, wt - i, K, M, used | 1); } else { ans += solve(dp, wt - i, K, M, used); } } return dp[wt][used] = ans; } let W = 3, K = 3, M = 2; let dp = new Array(W + 1); for (let i = 0; i < W + 1; i++) { dp[i] = new Array(2); for (let j = 0; j < 2; j++) { dp[i][j] = -1; } } document.write(solve(dp, W, K, M, 0) + "</br>"); // This code is contributed by suresh07.</script> |
Output
3
Time Complexity: O(W * K)
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!
