Dado un árbol binario infinito completo con raíz en el Node 1 , donde cada i -ésimo Node tiene dos hijos, con valores 2 * i y 2 * (i + 1) . Dada otra array arr[] que consiste en N enteros positivos, la tarea para cada elemento de la array arr[i] es encontrar la suma de los valores de Node que ocurren en una ruta desde el Node raíz hasta el Node arr[i] .
Ejemplos:
Entrada: arr[] = {3, 10}
Salida: 4 18
Explicación:
Node 3: La ruta es 3 -> 1. Por lo tanto, la suma de la ruta es 4.
Node 10: La ruta es 10 -> 5 -> 2 -> 1. Por lo tanto, la suma de los Nodes es 18.Entrada: arr[] = {1, 4, 20}
Salida: 1 7 38
Explicación:
Node 1: La ruta es 1. Por lo tanto, la suma de la ruta es 1.
Node 4: La ruta es 4 -> 2 -> 1. Por lo tanto, la suma de los Nodes es 7.
Node 20: El camino es 20 -> 10 -> 5 -> 2 -> 1. Por lo tanto, la suma de los Nodes es 38.
Enfoque ingenuo: el enfoque más simple es realizar DFS Traversal para cada elemento de array arr[i] para encontrar su ruta desde el Node actual hasta la raíz e imprimir la suma de los valores de Node en esa ruta.
Complejidad Temporal: O(N * H), donde H es la altura máxima del árbol.
Espacio Auxiliar: O(H)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de la observación de que el padre del Node con valor N contiene el valor N/2 . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos sumOfNode , para almacenar la suma de Nodes en una ruta.
- Recorra la array arr[i] y realice los siguientes pasos:
- Para cada elemento arr[i] , actualice el valor de sumOfNode como sumOfNode + X y actualice arr[i] como arr[i] / 2 .
- Repita los pasos anteriores mientras arr[i] sea mayor que 0 .
- Imprime el valor de sumOfNode como resultado para cada elemento de array arr[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <vector>
using namespace std;
// Function to find the sum of the
// path from root to the current node
void sumOfNodeInAPath(int node_value)
{
// Sum of nodes in the path
int sum_of_node = 0;
// Iterate until root is reached
while (node_value) {
sum_of_node += node_value;
// Update the node value
node_value /= 2;
}
// Print the resultant sum
cout << sum_of_node;
return;
}
// Function to print the path
// sum for each query
void findSum(vector<int> Q)
{
// Traverse the queries
for (int i = 0; i < Q.size(); i++) {
int node_value = Q[i];
sumOfNodeInAPath(node_value);
cout << " ";
}
}
// Driver Code
int main()
{
vector<int> arr = { 1, 5, 20, 100 };
findSum(arr);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.ArrayList;
class GFG {
// Function to find the sum of the
// path from root to the current node
public static void sumOfNodeInAPath(int node_value)
{
// Sum of nodes in the path
int sum_of_node = 0;
// Iterate until root is reached
while (node_value > 0) {
sum_of_node += node_value;
// Update the node value
node_value /= 2;
}
// Print the resultant sum
System.out.print(sum_of_node);
}
// Function to print the path
// sum for each query
public static void findSum(ArrayList<Integer> Q)
{
// Traverse the queries
for (int i = 0; i < Q.size(); i++) {
int node_value = Q.get(i);
sumOfNodeInAPath(node_value);
System.out.print(" ");
}
}
// Driver Code
public static void main(String[] args)
{
// arraylist to store integers
ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(5);
arr.add(20);
arr.add(100);
findSum(arr);
}
}
// This code is contributed by aditya7409.
Python3
# Python program for the above approach # Function to find the sum of the # path from root to the current node def sumOfNodeInAPath(node_value): # Sum of nodes in the path sum_of_node = 0 # Iterate until root is reached while (node_value): sum_of_node += node_value # Update the node value node_value //= 2 # Print the resultant sum print(sum_of_node, end = " ") # Function to print the path # sum for each query def findSum(Q): # Traverse the queries for i in range(len(Q)): node_value = Q[i] sumOfNodeInAPath(node_value) print(end = "") # Driver Code arr = [1, 5, 20, 100] findSum(arr) # This code is contributed by shubhamsingh10
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the sum of the
// path from root to the current node
public static void sumOfNodeInAPath(int node_value)
{
// Sum of nodes in the path
int sum_of_node = 0;
// Iterate until root is reached
while (node_value > 0) {
sum_of_node += node_value;
// Update the node value
node_value /= 2;
}
// Print the resultant sum
Console.Write(sum_of_node);
}
// Function to print the path
// sum for each query
public static void findSum(List<int> Q)
{
// Traverse the queries
for (int i = 0; i < Q.Count ; i++) {
int node_value = Q[i];
sumOfNodeInAPath(node_value);
Console.Write(" ");
}
}
// Driver Code
static public void Main()
{
// arraylist to store integers
List<int> arr = new List<int>();
arr.Add(1);
arr.Add(5);
arr.Add(20);
arr.Add(100);
findSum(arr);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program to count frequencies of array items
// Function to find the sum of the
// path from root to the current node
function sumOfNodeInAPath(node_value)
{
// Sum of nodes in the path
let sum_of_node = 0;
// Iterate until root is reached
while (node_value) {
sum_of_node += node_value;
// Update the node value
node_value = Math.floor(node_value / 2 );
}
// Print the resultant sum
document.write(sum_of_node);
return;
}
// Function to print the path
// sum for each query
function findSum( Q)
{
// Traverse the queries
for (let i = 0; i < Q.length; i++) {
let node_value = Q[i];
sumOfNodeInAPath(node_value);
document.write(" ");
}
}
// Driver Code
let arr = [ 1, 5, 20, 100 ];
findSum(arr);
</script>
1 8 38 197
Complejidad temporal: O(N*log X), donde X es el elemento máximo del arreglo .
Espacio Auxiliar: O(1)