Find the number of leaf nodes in a perfect N-ary tree of height K.
Note: As the answer can be very large, return the answer modulo 109+7.
Examples:
Input: N = 2, K = 2
Output: 4
Explanation: A perfect Binary tree of height 2 has 4 leaf nodes.Input: N = 2, K = 1
Output: 2
Explanation: A perfect Binary tree of height 1 has 2 leaf nodes.
Approach: This problem can be solved based on the observation that the number of leaf nodes in a perfect N-ary tree with height K will be equal to NK. Use Modular exponentiation to calculate the power modulo 109+7.
Follow the steps mentioned below to implement the above idea.
- Initialize one variable res = 1.
- Keep on reducing the power (here K) by half and squaring the base (here N) until the power is positive.
- Also when the power is odd, multiply the result by the base.
- Take mod 109+7 in each step.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;const int mod = 1e9 + 7;// Find the number of leaf nodes in a// perfect k-ary tree of height mlong long karyTree(long long N, int K){ // Initialize variable long long res = 1; // Run until height is positive while (K > 0) { if (K & 1) res = (res * N) % mod; N = (N * N) % mod; K >>= 1; } // Return answer return res;}// Driver codeint main(){ int N = 2, K = 2; // Function call cout << karyTree(N, K); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { static final int mod = 1000000007; public static void main(String[] args) { int N = 2, K = 2; // Function call System.out.println(karyTree(N, K)); } public static long karyTree(long N, int K) { // Initialize variable long res = 1; // Run until height is positive while (K > 0) { if (K % 2 == 1) res = (res * N) % mod; N = (N * N) % mod; K >>= 1; } // Return answer return res; }}// This code is contributed by ishankhandelwals. |
Python3
# python code to implement the approachmod = 1e9 + 7# Find the number of leaf nodes in a# perfect k-ary tree of height mdef karyTree(N, K): # Initialize variable res = 1 # Run until height is positive while (K > 0): if (K & 1): res = (res * N) % mod N = (N * N) % mod K >>= 1 # Return answer return res# Driver codeN,K = 2,2# Function callprint(karyTree(N, K))# This code is contributed by ishankhandelwals |
C#
// C# code to implement the approachusing System;class GFG { static int mod = 1000000007; public static void Main() { int N = 2, K = 2; // Function call Console.Write(karyTree(N, K)); } static long karyTree(long N, int K) { // Initialize variable long res = 1; // Run until height is positive while (K > 0) { if (K % 2 == 1) res = (res * N) % mod; N = (N * N) % mod; K >>= 1; } // Return answer return res; }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript code to implement the approachconst mod = 1e9 + 7;// Find the number of leaf nodes in a// perfect k-ary tree of height mfunction karyTree(N, K){ // Initialize variable let res = 1; // Run until height is positive while (K > 0) { if (K & 1) res = (res * N) % mod; N = (N * N) % mod; K >>= 1; } // Return answer return res;}// Driver code let N = 2, K = 2; // Function call document.write(karyTree(N, K)); // This code is contributed by ishankhandelwals</script> |
Output
4
Time Complexity: O(logK)
Auxiliary Space: O(1)
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!
