Número posible de árboles que tienen N vértice

Dada una array arr[] de N enteros positivos. La tarea es encontrar el número de árboles posibles que tengan N vértices tales que la distancia entre el vértice 1 y el vértice i sea arr[i] . El número total de tales árboles puede ser muy grande, así que devuelva la respuesta con módulo 10 ⁹ + 7 .

Ejemplos:

Entrada: arr[] = {0, 1, 1, 2}
Salida: 2
Explicación:
A continuación se muestra el árbol:

Entrada: arr[] = { 0, 3, 2, 1, 2, 2, 1 }
Salida: 24

Enfoque ingenuo: a continuación se muestran los pasos:

Si A ₁ !=0 y si elemento de A ₂ . . . A _N es 0 , entonces el árbol no se podrá hacer, por lo que en este caso, el recuento de árboles será 0 .
Si tomamos el primer Node como Node raíz, todos los Nodes en el nivel 1 deben ser hijos del Node raíz y todos los Nodes en el nivel 2 deben ser hijos de los Nodes de 1 nivel, por lo que solo hay una posibilidad de colocarlos en el nivel: sabio.
Ahora, sea x el número de Nodes en el i ^-ésimo nivel e y es el número de Nodes en (i + 1) el ^ésimo nivel, por lo que el número de posibilidades de organizar los Nodes en el nivel i y (i + 1) es x ^y .
Por lo tanto, el conteo de árboles será X _i^X_{^{(i + 1)}} donde X _i es el número de Nodes en el i ^-ésimo nivel .

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
 
// Function to count the total number
// of trees possible
int NumberOfTrees(int arr[], int N)
{
    // Find the max element in the
    // given array
    int maxElement = *max_element(arr, arr + N);
 
    // Level array store the number of
    // nodes on level i initially all
    // values are zero
    int level[maxElement + 1] = { 0 };
    for (int i = 0; i < N; i++) {
 
        level[arr[i]]++;
    }
 
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1) {
 
        return 0;
    }
 
    // To store the count of trees
    int ans = 1;
 
    // Iterate until maxElement
    for (int i = 0; i < maxElement; i++) {
 
        // Calculate level[i]^level[i+1]
        for (int j = 0; j < level[i + 1]; j++) {
 
            // Update the count of tree
            ans = (ans * level[i]) % mod;
        }
    }
 
    // Return the final count of trees
    return ans;
}
 
// Driver Code
int main()
{
    int N = 7;
 
    // Given array arr[]
    int arr[] = { 0, 3, 2, 1, 2, 2, 1 };
 
    // Function Call
    cout << NumberOfTrees(arr, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int mod = (int)(1e9 + 7);
 
// Function to count the total number
// of trees possible
static int NumberOfTrees(int arr[], int N)
{
     
    // Find the max element in the
    // given array
    int maxElement = Arrays.stream(arr).max().getAsInt();
 
    // Level array store the number of
    // nodes on level i initially all
    // values are zero
    int level[] = new int[maxElement + 1];
    for(int i = 0; i < N; i++)
    {
        level[arr[i]]++;
    }
 
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1)
    {
        return 0;
    }
 
    // To store the count of trees
    int ans = 1;
 
    // Iterate until maxElement
    for(int i = 0; i < maxElement; i++)
    {
         
        // Calculate level[i]^level[i+1]
        for (int j = 0; j < level[i + 1]; j++)
        {
             
            // Update the count of tree
            ans = (ans * level[i]) % mod;
        }
    }
 
    // Return the final count of trees
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7;
 
    // Given array arr[]
    int arr[] = { 0, 3, 2, 1, 2, 2, 1 };
 
    // Function call
    System.out.print(NumberOfTrees(arr, N));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
mod = int(1e9 + 7)
 
# Function to count the total number
# of trees possible
def NumberOfTrees(arr, N):
     
    # Find the max element in the
    # given array
    maxElement = max(arr);
 
    # Level array store the number of
    # Nodes on level i initially all
    # values are zero
    level = [0] * (maxElement + 1);
    for i in range(N):
        level[arr[i]] += 1;
 
    # In this case tree can not be created
    if (arr[0] != 0 or level[0] != 1):
        return 0;
 
    # To store the count of trees
    ans = 1;
 
    # Iterate until maxElement
    for i in range(maxElement):
 
        # Calculate level[i]^level[i+1]
        for j in range(level[i + 1]):
             
            # Update the count of tree
            ans = (ans * level[i]) % mod;
 
    # Return the final count of trees
    return ans;
 
# Driver Code
if __name__ == '__main__':
     
    N = 7;
 
    # Given array arr
    arr = [ 0, 3, 2, 1, 2, 2, 1 ];
 
    # Function call
    print(NumberOfTrees(arr, N));
 
# This code is contributed by shikhasingrajput

C#

// C# program for the above approach
using System;
using System.Linq;
class GFG{
     
static int mod = (int)(1e9 + 7);
 
// Function to count the total number
// of trees possible
static int NumberOfTrees(int []arr, int N)
{
     
    // Find the max element in the
    // given array
    int maxElement = arr.Max();
 
    // Level array store the number of
    // nodes on level i initially all
    // values are zero
    int []level = new int[maxElement + 1];
    for(int i = 0; i < N; i++)
    {
        level[arr[i]]++;
    }
 
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1)
    {
        return 0;
    }
 
    // To store the count of trees
    int ans = 1;
 
    // Iterate until maxElement
    for(int i = 0; i < maxElement; i++)
    {
         
        // Calculate level[i]^level[i+1]
        for (int j = 0; j < level[i + 1]; j++)
        {
             
            // Update the count of tree
            ans = (ans * level[i]) % mod;
        }
    }
 
    // Return the readonly count of trees
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 7;
 
    // Given array []arr
    int []arr = { 0, 3, 2, 1, 2, 2, 1 };
 
    // Function call
    Console.Write(NumberOfTrees(arr, N));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// JavaScript program for the
// above approach
 
let mod = (1e9 + 7);
   
// Function to count the total number
// of trees possible
function NumberOfTrees(arr, N)
{
       
    // Find the max element in the
    // given array
    let maxElement = Math.max(...arr);
   
    // Level array store the number of
    // nodes on level i initially all
    // values are zero
    let level = Array.from({length: maxElement + 1}, (_, i) => 0);
    for(let i = 0; i < N; i++)
    {
        level[arr[i]]++;
    }
   
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1)
    {
        return 0;
    }
   
    // To store the count of trees
    let ans = 1;
   
    // Iterate until maxElement
    for(let i = 0; i < maxElement; i++)
    {
           
        // Calculate level[i]^level[i+1]
        for (let j = 0; j < level[i + 1]; j++)
        {
               
            // Update the count of tree
            ans = (ans * level[i]) % mod;
        }
    }
   
    // Return the final count of trees
    return ans;
}
// Driver Code
 
    let N = 7;
   
    // Given array arr[]
    let arr = [ 0, 3, 2, 1, 2, 2, 1 ];
   
    // Function call
    document.write(NumberOfTrees(arr, N));
 
</script>

Producción:

Complejidad temporal: O(N*K) donde K es el número de vértices en un nivel.
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante la optimización del valor de (ans*level[i]) mediante la exponenciación modular . A continuación se muestran los pasos:

Si el exponente es impar, hazlo par restándole 1 y multiplica la base por la respuesta.
Si el exponente es par, divide el exponente por 2 y eleva al cuadrado la base.
Devuelve 1 cuando el exponente se convierte en 0.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
 
// Function that finds the value of x^y
// using Modular Exponentiation
int power(int x, int y)
{
    // Base Case
    if (y == 0)
        return 1;
 
    int p = power(x, y / 2) % mod;
 
    p = (p * p) % mod;
 
    // If y is odd, multiply
    // x with result
    if (y & 1)
        p = (x * p) % mod;
 
    // Return the value
    return p;
}
 
// Function that counts the total
// number of trees possible
int NumberOfTrees(int arr[], int N)
{
 
    // Find the max element in array
    int maxElement
        = *max_element(arr, arr + N);
 
    // Level array store the number nodes
    // on level i initially all values are 0
    int level[maxElement + 1] = { 0 };
 
    for (int i = 0; i < N; i++) {
        level[arr[i]]++;
    }
 
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1) {
 
        return 0;
    }
 
    int ans = 1;
 
    for (int i = 0; i < maxElement; i++) {
 
        // Calculate level[i]^level[i+1]
        ans = (ans * power(level[i],
                           level[i + 1]))
              % mod;
    }
 
    // Return the final count
    return ans;
}
 
// Driver Code
int main()
{
    int N = 7;
 
    // Given array arr[]
    int arr[] = { 0, 3, 2, 1, 2, 2, 1 };
 
    // Function Call
    cout << NumberOfTrees(arr, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static int mod = (int)1e9 + 7;
 
// Function that finds the value of x^y
// using Modular Exponentiation
static int power(int x, int y)
{
     
    // Base Case
    if (y == 0)
        return 1;
 
    int p = power(x, y / 2) % mod;
 
    p = (p * p) % mod;
 
    // If y is odd, multiply
    // x with result
    if ((y & 1) != 0)
        p = (x * p) % mod;
 
    // Return the value
    return p;
}
 
// Function that counts the total
// number of trees possible
static int NumberOfTrees(int arr[], int N)
{
 
    // Find the max element in array
    int maxElement = Arrays.stream(arr).max().getAsInt();
 
    // Level array store the number nodes
    // on level i initially all values are 0
    int []level = new int[maxElement + 1];
 
    for(int i = 0; i < N; i++)
    {
        level[arr[i]]++;
    }
 
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1)
    {
        return 0;
    }
     
    int ans = 1;
 
    for(int i = 0; i < maxElement; i++)
    {
        // Calculate level[i]^level[i+1]
        ans = (ans * power(level[i],
                           level[i + 1])) % mod;
    }
 
    // Return the final count
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 7;
 
    // Given array arr[]
    int arr[] = { 0, 3, 2, 1, 2, 2, 1 };
 
    // Function call
    System.out.print(NumberOfTrees(arr, N));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
mod = int(1e9 + 7)
 
# Function that finds the value of x^y
# using Modular Exponentiation
def power(x, y):
 
    # Base Case
    if(y == 0):
        return 1
 
    p = power(x, y // 2) % mod
 
    p = (p * p) % mod
 
    # If y is odd, multiply
    # x with result
    if(y & 1):
        p = (x * p) % mod
 
    # Return the value
    return p
 
# Function that counts the total
# number of trees possible
def NumberOfTrees(arr, N):
 
    # Find the max element in array
    maxElement = max(arr)
 
    # Level array store the number nodes
    # on level i initially all values are 0
    level = [0] * (maxElement + 1)
 
    for i in range(N):
        level[arr[i]] += 1
 
    # In this case tree can not be created
    if(arr[0] != 0 or level[0] != 1):
        return 0
 
    ans = 1
 
    for i in range(maxElement):
 
        # Calculate level[i]^level[i+1]
        ans = (ans * power(level[i],
                           level[i + 1])) % mod
 
    # Return the final count
    return ans
 
# Driver Code
N = 7
 
# Given Queries
arr = [ 0, 3, 2, 1, 2, 2, 1 ]
 
# Function call
print(NumberOfTrees(arr, N))
 
# This code is contributed by Shivam Singh

C#

// C# program for the above approach
using System;
using System.Linq;
 
class GFG{
     
static int mod = (int)1e9 + 7;
 
// Function that finds the value of x^y
// using Modular Exponentiation
static int power(int x, int y)
{
     
    // Base Case
    if (y == 0)
        return 1;
 
    int p = power(x, y / 2) % mod;
 
    p = (p * p) % mod;
 
    // If y is odd, multiply
    // x with result
    if ((y & 1) != 0)
        p = (x * p) % mod;
 
    // Return the value
    return p;
}
 
// Function that counts the total
// number of trees possible
static int NumberOfTrees(int []arr, int N)
{
 
    // Find the max element in array
    int maxElement = arr.Max();
 
    // Level array store the number nodes
    // on level i initially all values are 0
    int []level = new int[maxElement + 1];
 
    for(int i = 0; i < N; i++)
    {
        level[arr[i]]++;
    }
 
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1)
    {
        return 0;
    }
     
    int ans = 1;
 
    for(int i = 0; i < maxElement; i++)
    {
         
        // Calculate level[i]^level[i+1]
        ans = (ans * power(level[i],
                           level[i + 1])) % mod;
    }
 
    // Return the readonly count
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 7;
 
    // Given array []arr
    int []arr = { 0, 3, 2, 1, 2, 2, 1 };
 
    // Function call
    Console.Write(NumberOfTrees(arr, N));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript program for the
// above approach
 
let mod = 1e9 + 7;
  
// Function that finds the value of x^y
// using Modular Exponentiation
function power(x, y)
{
      
    // Base Case
    if (y == 0)
        return 1;
  
    let p = power(x, y / 2) % mod;
  
    p = (p * p) % mod;
  
    // If y is odd, multiply
    // x with result
    if ((y & 1) != 0)
        p = (x * p) % mod;
  
    // Return the value
    return p;
}
  
// Function that counts the total
// number of trees possible
function NumberOfTrees(arr, N)
{
  
    // Find the max element in array
    let maxElement = Math.max(...arr);
  
    // Level array store the number nodes
    // on level i initially all values are 0
    let level = Array(maxElement + 1).fill(0);
  
    for(let i = 0; i < N; i++)
    {
        level[arr[i]]++;
    }
  
    // In this case tree can not be created
    if (arr[0] != 0 || level[0] != 1)
    {
        return 0;
    }
      
    let ans = 1;
  
    for(let i = 0; i < maxElement; i++)
    {
        // Calculate level[i]^level[i+1]
        ans = (ans * power(level[i],
                           level[i + 1])) % mod;
    }
  
    // Return the final count
    return ans;
}
  
// Driver Code
 
    let N = 7;
  
    // Given array arr[]
    let arr = [ 0, 3, 2, 1, 2, 2, 1 ];
  
    // Function call
    document.write(NumberOfTrees(arr, N));
    
   // This code is contributed by decode2207.
</script>

Producción:

Complejidad temporal: O(N*log K) donde K es el número de vértices en un nivel.
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por __mahakal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta