Número de Nodes hoja en un árbol N-ario perfecto de altura K

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 ⁹ +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 ⁹ +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 ⁹ +7 en cada paso.

A continuación se muestra la implementación del enfoque anterior:

// 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 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.

# 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# 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.

<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)