Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Variety of leaf nodes in an ideal N-ary tree of top Okay

[ad_1]

Discover the variety of leaf nodes in an ideal N-ary tree of top Okay.

Notice: As the reply might be very giant, return the reply modulo 109+7.

Examples:

Enter: N = 2, Okay = 2
Output: 4
Clarification: An ideal Binary tree of top 2 has 4 leaf nodes. 

Enter: N = 2, Okay = 1
Output: 2
Clarification: An ideal Binary tree of top 1 has 2 leaf nodes.

 

Method: This drawback might be solved based mostly on the commentary that the variety of leaf nodes in an ideal N-ary tree with top Okay shall be equal to NOkay. Use Modular exponentiation to calculate the ability modulo 109+7.

Observe the steps talked about under to implement the above concept.

  • Initialize one variable res = 1.
  • Carry on lowering the ability (right here Okay) by half and squaring the base (right here N) till the ability is optimistic.
  • Additionally when the ability is odd, multiply the consequence by the base.
  • Take mod 109+7 in every step.

Beneath is the implementation of the above method:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

const int mod = 1e9 + 7;

  

lengthy lengthy karyTree(lengthy lengthy N, int Okay)

{

    

    lengthy lengthy res = 1;

  

    

    whereas (Okay > 0) {

        if (Okay & 1)

            res = (res * N) % mod;

        N = (N * N) % mod;

        Okay >>= 1;

    }

  

    

    return res;

}

  

int fundamental()

{

    int N = 2, Okay = 2;

  

    

    cout << karyTree(N, Okay);

    return 0;

}

Time Complexity: O(logK)
Auxiliary House: O(1)

[ad_2]

Leave a Reply