Encuentre el número de Nodes hoja en un árbol N-ario perfecto de altura K .
Nota: Como la respuesta puede ser muy grande, devuelva la respuesta módulo 10 9 +7 .
Ejemplos:
Entrada: N = 2, K = 2
Salida: 4
Explicación: Un árbol binario perfecto de altura 2 tiene 4 Nodes de hoja.Entrada: N = 2, K = 1
Salida: 2
Explicación: Un árbol binario perfecto de altura 1 tiene 2 Nodes de hoja.
Enfoque: Este problema se puede resolver basándose en la observación de que el número de Nodes de hoja en un árbol N-ario perfecto con altura K será igual a N K . Utilice la exponenciación modular para calcular el módulo de potencia 10 9 +7 .
Siga los pasos mencionados a continuación para implementar la idea anterior.
- Inicialice una variable res = 1.
- Sigue reduciendo la potencia (aquí K ) a la mitad y elevando al cuadrado la base (aquí N ) hasta que la potencia sea positiva.
- También cuando la potencia es impar, multiplica el resultado por la base .
- Tome mod 10 9 +7 en cada paso.
A continuación se muestra la implementación del enfoque anterior:
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 m long 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 code int main() { int N = 2, K = 2; // Function call cout << karyTree(N, K); return 0; }
Java
// Java code to implement the approach import 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 approach mod = 1e9 + 7 # Find the number of leaf nodes in a # perfect k-ary tree of height m def 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 code N,K = 2,2 # Function call print(karyTree(N, K)) # This code is contributed by ishankhandelwals
C#
// C# code to implement the approach using 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 approach const mod = 1e9 + 7; // Find the number of leaf nodes in a // perfect k-ary tree of height m function 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>
4
Complejidad de Tiempo: O(logK)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA