Dada una array de n enteros, cada entero es mayor que 1. La tarea es encontrar el número de árboles binarios completos a partir de los enteros dados, de modo que cada valor de Node hoja que no sea de Node sea el producto de su valor secundario. Dado eso, cada entero se puede usar varias veces en un árbol binario completo.
Ejemplos:
Input : arr[] = { 2, 3, 4, 6 }.
Output : 7
There can be 7 full binary tree with the given product property.
// Four trees with single nodes
2 3 4 6
// Three trees with three nodes
4 ,
/ \
2 2
6 ,
/ \
2 3
6
/ \
3 2
Encontramos el valor máximo en una array dada y creamos una array para almacenar la presencia de elementos en esta array. La idea es que, para todos los múltiplos de cada entero menor que el valor máximo de la array, intente hacer un árbol binario completo si el múltiplo está presente en la array.
Observe que para cualquier árbol binario completo con una propiedad dada, los valores más pequeños siempre estarán en el último nivel. Entonces, intente encontrar el número de dicho árbol binario completo desde el valor mínimo de la array hasta el valor máximo de la array.
Algoritmo:
- Inicialice el número posible de dicho árbol binario completo para cada elemento igual a 1. Dado que un solo Node también contribuye a la respuesta.
- Para cada elemento de la array, arr[i], desde el valor mínimo hasta el valor máximo de la array.
- Para cada múltiplo de arr[i], encuentre si el múltiplo está presente o no.
- En caso afirmativo, entonces el número de dicho árbol binario completo posible para el múltiplo de arr[i], digamos m, es igual al producto del número de dicho árbol binario completo posible de arr[i] y el número de dicho árbol binario completo posible de arr[i]/m.
Implementación:
C++
// C++ program to find number of full binary tree
// such that each node is product of its children.
#include<bits/stdc++.h>
using namespace std;
// Return the number of all possible full binary
// tree with given product property.
int numoffbt(int arr[], int n)
{
// Finding the minimum and maximum values in
// given array.
int maxvalue = INT_MIN, minvalue = INT_MAX;
for (int i = 0; i < n; i++)
{
maxvalue = max(maxvalue, arr[i]);
minvalue = min(minvalue, arr[i]);
}
int mark[maxvalue + 2];
int value[maxvalue + 2];
memset(mark, 0, sizeof(mark));
memset(value, 0, sizeof(value));
// Marking the presence of each array element
// and initialising the number of possible
// full binary tree for each integer equal
// to 1 because single node will also
// contribute as a full binary tree.
for (int i = 0; i < n; i++)
{
mark[arr[i]] = 1;
value[arr[i]] = 1;
}
// From minimum value to maximum value of array
// finding the number of all possible Full
// Binary Trees.
int ans = 0;
for (int i = minvalue; i <= maxvalue; i++)
{
// Find if value present in the array
if (mark[i])
{
// For each multiple of i, less than
// equal to maximum value of array
for (int j = i + i;
j <= maxvalue && j/i <= i; j += i)
{
// If multiple is not present in the
// array then continue.
if (!mark[j])
continue;
// Finding the number of possible Full
// binary trees for multiple j by
// multiplying number of possible Full
// binary tree from the number i and
// number of possible Full binary tree
// from i/j.
value[j] = value[j] + (value[i] * value[j/i]);
// Condition for possibility when left
// child became right child and vice versa.
if (i != j/i)
value[j] = value[j] + (value[i] * value[j/i]);
}
}
ans += value[i];
}
return ans;
}
// Driven Program
int main()
{
int arr[] = { 2, 3, 4, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << numoffbt(arr, n) << endl;
return 0;
}
Java
// Java program to find number of full
// binary tree such that each node is
// product of its children.
import java.util.Arrays;
class GFG {
// Return the number of all possible
// full binary tree with given product
// property.
static int numoffbt(int arr[], int n)
{
// Finding the minimum and maximum
// values in given array.
int maxvalue = -2147483647;
int minvalue = 2147483647;
for (int i = 0; i < n; i++)
{
maxvalue = Math.max(maxvalue, arr[i]);
minvalue = Math.min(minvalue, arr[i]);
}
int mark[] = new int[maxvalue + 2];
int value[] = new int[maxvalue + 2];
Arrays.fill(mark, 0);
Arrays.fill(value, 0);
// Marking the presence of each array element
// and initialising the number of possible
// full binary tree for each integer equal
// to 1 because single node will also
// contribute as a full binary tree.
for (int i = 0; i < n; i++)
{
mark[arr[i]] = 1;
value[arr[i]] = 1;
}
// From minimum value to maximum value of array
// finding the number of all possible Full
// Binary Trees.
int ans = 0;
for (int i = minvalue; i <= maxvalue; i++)
{
// Find if value present in the array
if (mark[i] != 0)
{
// For each multiple of i, less than
// equal to maximum value of array
for (int j = i + i;
j <= maxvalue && j/i <= i; j += i)
{
// If multiple is not present in
// the array then continue.
if (mark[j] == 0)
continue;
// Finding the number of possible
// Full binary trees for multiple
// j by multiplying number of
// possible Full binary tree from
// the number i and number of
// possible Full binary tree from i/j.
value[j] = value[j] + (value[i]
* value[j/i]);
// Condition for possibility when
// left child became right child
// and vice versa.
if (i != j / i)
value[j] = value[j] + (value[i]
* value[j/i]);
}
}
ans += value[i];
}
return ans;
}
//driver code
public static void main (String[] args)
{
int arr[] = { 2, 3, 4, 6 };
int n = arr.length;
System.out.print(numoffbt(arr, n));
}
}
//This code is contributed by Anant Agarwal.
Python3
# Python3 program to find number of # full binary tree such that each node # is product of its children. # Return the number of all possible full # binary tree with given product property. def numoffbt(arr, n): # Finding the minimum and maximum # values in given array. maxvalue = -2147483647 minvalue = 2147483647 for i in range(n): maxvalue = max(maxvalue, arr[i]) minvalue = min(minvalue, arr[i]) mark = [0 for i in range(maxvalue + 2)] value = [0 for i in range(maxvalue + 2)] # Marking the presence of each array element # and initialising the number of possible # full binary tree for each integer equal # to 1 because single node will also # contribute as a full binary tree. for i in range(n): mark[arr[i]] = 1 value[arr[i]] = 1 # From minimum value to maximum value # of array finding the number of all # possible Full Binary Trees. ans = 0 for i in range(minvalue, maxvalue + 1): # Find if value present in the array if (mark[i] != 0): # For each multiple of i, less than # equal to maximum value of array j = i + i while(j <= maxvalue and j // i <= i): # If multiple is not present in the # array then continue. if (mark[j] == 0): continue # Finding the number of possible Full # binary trees for multiple j by # multiplying number of possible Full # binary tree from the number i and # number of possible Full binary tree # from i/j. value[j] = value[j] + (value[i] * value[j // i]) # Condition for possibility when left # child became right child and vice versa. if (i != j // i): value[j] = value[j] + (value[i] * value[j // i]) j += i ans += value[i] return ans # Driver Code arr = [ 2, 3, 4, 6 ] n = len(arr) print(numoffbt(arr, n)) # This code is contributed by Anant Agarwal.
C#
// C# program to find number of
// full binary tree such that each
// node is product of its children.
using System;
class GFG
{
// Return the number of all possible full binary
// tree with given product property.
static int numoffbt(int []arr, int n)
{
// Finding the minimum and maximum values in
// given array.
int maxvalue = -2147483647, minvalue = 2147483647;
for (int i = 0; i < n; i++)
{
maxvalue = Math.Max(maxvalue, arr[i]);
minvalue = Math.Min(minvalue, arr[i]);
}
int []mark=new int[maxvalue + 2];
int []value=new int[maxvalue + 2];
for(int i = 0;i < maxvalue + 2; i++)
{
mark[i]=0;
value[i]=0;
}
// Marking the presence of each array element
// and initialising the number of possible
// full binary tree for each integer equal
// to 1 because single node will also
// contribute as a full binary tree.
for (int i = 0; i < n; i++)
{
mark[arr[i]] = 1;
value[arr[i]] = 1;
}
// From minimum value to maximum value of array
// finding the number of all possible Full
// Binary Trees.
int ans = 0;
for (int i = minvalue; i <= maxvalue; i++)
{
// Find if value present in the array
if (mark[i] != 0)
{
// For each multiple of i, less than
// equal to maximum value of array
for (int j = i + i;
j <= maxvalue && j/i <= i; j += i)
{
// If multiple is not present in the
// array then continue.
if (mark[j] == 0)
continue;
// Finding the number of possible Full
// binary trees for multiple j by
// multiplying number of possible Full
// binary tree from the number i and
// number of possible Full binary tree
// from i/j.
value[j] = value[j] + (value[i] * value[j/i]);
// Condition for possibility when left
// child became right child and vice versa.
if (i != j/i)
value[j] = value[j] + (value[i] * value[j/i]);
}
}
ans += value[i];
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 2, 3, 4, 6 };
int n = arr.Length;
Console.Write(numoffbt(arr, n));
}
}
// This code is contributed by Anant Agarwal.
Javascript
<script>
// Javascript program to find number of full binary tree
// such that each node is product of its children.
// Return the number of all possible full binary
// tree with given product property.
function numoffbt(arr, n) {
// Finding the minimum and maximum values in
// given array.
let maxvalue = Number.MIN_SAFE_INTEGER, minvalue = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < n; i++) {
maxvalue = Math.max(maxvalue, arr[i]);
minvalue = Math.min(minvalue, arr[i]);
}
let mark = new Array(maxvalue + 2).fill(0);
let value = new Array(maxvalue + 2).fill(0);
// Marking the presence of each array element
// and initialising the number of possible
// full binary tree for each integer equal
// to 1 because single node will also
// contribute as a full binary tree.
for (let i = 0; i < n; i++) {
mark[arr[i]] = 1;
value[arr[i]] = 1;
}
// From minimum value to maximum value of array
// finding the number of all possible Full
// Binary Trees.
let ans = 0;
for (let i = minvalue; i <= maxvalue; i++) {
// Find if value present in the array
if (mark[i]) {
// For each multiple of i, less than
// equal to maximum value of array
for (let j = i + i;
j <= maxvalue && j / i <= i; j += i) {
// If multiple is not present in the
// array then continue.
if (!mark[j])
continue;
// Finding the number of possible Full
// binary trees for multiple j by
// multiplying number of possible Full
// binary tree from the number i and
// number of possible Full binary tree
// from i/j.
value[j] = value[j] + (value[i] * value[j / i]);
// Condition for possibility when left
// child became right child and vice versa.
if (i != j / i)
value[j] = value[j] + (value[i] * value[j / i]);
}
}
ans += value[i];
}
return ans;
}
// Driven Program
let arr = [2, 3, 4, 6];
let n = arr.length;
document.write(numoffbt(arr, n) + "<br>");
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
7
Este artículo es una contribución de Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA