Dado un número entero N que debe estar presente como un valor en un Node en el último nivel de un árbol con raíz en 1 que tiene Nodes numerados desde la raíz hasta el último nivel en incrementos de 1 . Los Nodes en cada nivel impar contienen 2 hijos y los Nodes en cada nivel par contienen 4 hijos . La tarea es encontrar la suma de los valores de los Nodes en el camino desde la raíz hasta el Node N.
Ejemplos:
Entrada: N = 13
Salida: 20
Explicación: El recorrido desde la raíz 1 al Node 13 es 1 -> 2 -> 4 -> 13. Por lo tanto, la suma de todos los Nodes en la ruta = 1 + 2 + 4 + 13 = 20.Entrada: N = 124
Salida: 193
Explicación: El recorrido desde la raíz 1 hasta el Node 124 es 1 -> 2 -> 6 -> 16 -> 44 -> 124. Por lo tanto, la suma de todos los Nodes en la ruta = 1 + 2 + 6 + 16 + 44 + 124 = 193.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array para almacenar el número de Nodes presentes en cada nivel del Árbol , es decir, {1, 2, 8, 16, 64, 128…} y guárdelo.
- Calcule la suma del prefijo de la array, es decir, {1 3 11 27 91 219 …….}
- Encuentre el ind de índice en la array de suma de prefijos que excede o es igual a N usando lower_bound() . Por lo tanto, ind indica el número de niveles que deben atravesarse para llegar al Node N.
- Inicialice una variable temp = N y dos variables final_ans = 0 y val .
- Disminuya ind hasta que sea menor o igual a 1 y siga actualizando val = temp – prefix[ind – 1] .
- Actualice temp a prefix[ind – 2] + (val + 1) / 2 si ind es impar .
- De lo contrario, actualice prefix[ind – 2] + (val + 3) / 4 si ind es par .
- Después de completar los pasos anteriores, agregue N + 1 a final_ans e imprímalo como la respuesta requerida.
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;
typedef long long ll;
// Function to find sum of all
// nodes from root to N
ll sumOfPathNodes(ll N)
{
// If N is equal to 1
if (N == 1) {
return 1;
}
// If N is equal to 2 or 3
else if (N == 2 || N == 3) {
return N + 1;
}
// Stores the number of
// nodes at (i + 1)-th level
vector<ll> arr;
arr.push_back(1);
// Stores the number of nodes
ll k = 1;
// Stores if the current
// level is even or odd
bool flag = true;
while (k < N) {
// If level is odd
if (flag == true) {
k *= 2;
flag = false;
}
// If level is even
else {
k *= 4;
flag = true;
}
// If level with
// node N is reached
if (k > N) {
break;
}
// Push into vector
arr.push_back(k);
}
ll len = arr.size();
vector<ll> prefix(len);
prefix[0] = 1;
// Compute prefix sums of count
// of nodes in each level
for (ll i = 1; i < len; ++i) {
prefix[i] = arr[i] + prefix[i - 1];
}
vector<ll>::iterator it
= lower_bound(prefix.begin(),
prefix.end(), N);
// Stores the level in which
// node N s present
ll ind = it - prefix.begin();
// Stores the required sum
ll final_ans = 0;
ll temp = N;
while (ind > 1) {
ll val = temp - prefix[ind - 1];
if (ind % 2 != 0) {
temp = prefix[ind - 2]
+ (val + 1) / 2;
}
else {
temp = prefix[ind - 2]
+ (val + 3) / 4;
}
--ind;
// Add temp to the sum
final_ans += temp;
}
final_ans += (N + 1);
return final_ans;
}
// Driver Code
int main()
{
ll N = 13;
// Function Call
cout << sumOfPathNodes(N) << endl;
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to find sum of
// aint nodes from root to N
static int sumOfPathNodes(int N)
{
// If N is equal to 1
if (N == 1)
{
return 1;
}
// If N is equal to
// 2 or 3
else if (N == 2 ||
N == 3)
{
return N + 1;
}
// Stores the number of
// nodes at (i + 1)-th level
Vector<Integer> arr =
new Vector<>();
arr.add(1);
// Stores the number
// of nodes
int k = 1;
// Stores if the current
// level is even or odd
boolean flag = true;
while (k < N)
{
// If level is odd
if (flag == true)
{
k *= 2;
flag = false;
}
// If level is even
else
{
k *= 4;
flag = true;
}
// If level with
// node N is reached
if (k > N)
{
break;
}
// Push into vector
arr.add(k);
}
int len = arr.size();
int[] prefix = new int[len];
prefix[0] = 1;
// Compute prefix sums of
// count of nodes in each
// level
for (int i = 1; i < len; ++i)
{
prefix[i] = arr.get(i) +
prefix[i - 1];
}
int it = lowerBound(prefix, 0,
len, N) + 1;
// Stores the level in which
// node N s present
int ind = it - prefix[0];
// Stores the required sum
int final_ans = 0;
int temp = N;
while (ind > 1)
{
int val = temp -
prefix[ind - 1];
if (ind % 2 != 0)
{
temp = prefix[ind - 2] +
(val + 1) / 2;
}
else
{
temp = prefix[ind - 2] +
(val + 3) / 4;
}
--ind;
// Add temp to the sum
final_ans += temp;
}
final_ans += (N + 1);
return final_ans;
}
static int lowerBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Driver Code
public static void main(String[] args)
{
int N = 13;
// Function Call
System.out.print(
sumOfPathNodes(N) + "\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach from bisect import bisect_left, bisect # Function to find sum of all # nodes from root to N def sumOfPathNodes(N): # If N is equal to 1 if (N == 1): return 1 # If N is equal to 2 or 3 elif (N == 2 or N == 3): return N + 1 # Stores the number of # nodes at (i + 1)-th level arr = [] arr.append(1) # Stores the number of nodes k = 1 # Stores if the current # level is even or odd flag = True while (k < N): # If level is odd if (flag == True): k *= 2 flag = False # If level is even else: k *= 4 flag = True # If level with # node N is reached if (k > N): break # Push into vector arr.append(k) lenn = len(arr) prefix = [0] * (lenn) prefix[0] = 1 # Compute prefix sums of count # of nodes in each level for i in range(1, lenn): prefix[i] = arr[i] + prefix[i - 1] it = bisect_left(prefix, N) # Stores the level in which # node N s present ind = it # Stores the required sum final_ans = 0 temp = N while (ind > 1): val = temp - prefix[ind - 1] if (ind % 2 != 0): temp = prefix[ind - 2] + (val + 1) // 2 else: temp = prefix[ind - 2] + (val + 3) // 4 ind -= 1 # Add temp to the sum final_ans += temp final_ans += (N + 1) return final_ans # Driver Code if __name__ == '__main__': N = 13 # Function Call print(sumOfPathNodes(N)) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find sum of
// aint nodes from root to N
static int sumOfPathNodes(int N)
{
// If N is equal to 1
if (N == 1)
{
return 1;
}
// If N is equal to
// 2 or 3
else if (N == 2 ||
N == 3)
{
return N + 1;
}
// Stores the number of
// nodes at (i + 1)-th level
List<int> arr = new List<int>();
arr.Add(1);
// Stores the number
// of nodes
int k = 1;
// Stores if the current
// level is even or odd
bool flag = true;
while (k < N)
{
// If level is odd
if (flag == true)
{
k *= 2;
flag = false;
}
// If level is even
else
{
k *= 4;
flag = true;
}
// If level with
// node N is reached
if (k > N)
{
break;
}
// Push into vector
arr.Add(k);
}
int len = arr.Count;
int[] prefix = new int[len];
prefix[0] = 1;
// Compute prefix sums of
// count of nodes in each
// level
for(int i = 1; i < len; ++i)
{
prefix[i] = arr[i] +
prefix[i - 1];
}
int it = lowerBound(prefix, 0,
len, N) + 1;
// Stores the level in which
// node N s present
int ind = it - prefix[0];
// Stores the required sum
int final_ans = 0;
int temp = N;
while (ind > 1)
{
int val = temp -
prefix[ind - 1];
if (ind % 2 != 0)
{
temp = prefix[ind - 2] +
(val + 1) / 2;
}
else
{
temp = prefix[ind - 2] +
(val + 3) / 4;
}
--ind;
// Add temp to the sum
final_ans += temp;
}
final_ans += (N + 1);
return final_ans;
}
static int lowerBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Driver Code
public static void Main(String[] args)
{
int N = 13;
// Function Call
Console.Write(sumOfPathNodes(N) + "\n");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find sum of
// aint nodes from root to N
function sumOfPathNodes(N)
{
// If N is equal to 1
if (N == 1)
{
return 1;
}
// If N is equal to
// 2 or 3
else if (N == 2 ||
N == 3)
{
return N + 1;
}
// Stores the number of
// nodes at (i + 1)-th level
let arr = [];
arr.push(1);
// Stores the number
// of nodes
let k = 1;
// Stores if the current
// level is even or odd
let flag = true;
while (k < N)
{
// If level is odd
if (flag == true)
{
k *= 2;
flag = false;
}
// If level is even
else
{
k *= 4;
flag = true;
}
// If level with
// node N is reached
if (k > N)
{
break;
}
// Push into vector
arr.push(k);
}
let len = arr.length;
let prefix = new Array(len);
prefix[0] = 1;
// Compute prefix sums of
// count of nodes in each
// level
for (let i = 1; i < len; ++i)
{
prefix[i] = arr[i] + prefix[i - 1];
}
let it = lowerBound(prefix, 0, len, N) + 1;
// Stores the level in which
// node N s present
let ind = it - prefix[0];
// Stores the required sum
let final_ans = 0;
let temp = N;
while (ind > 1)
{
let val = temp - prefix[ind - 1];
if (ind % 2 != 0)
{
temp = prefix[ind - 2] +
parseInt((val + 1) / 2, 10);
}
else
{
temp = prefix[ind - 2] +
parseInt((val + 3) / 4, 10);
}
--ind;
// Add temp to the sum
final_ans += temp;
}
final_ans += (N + 1);
return final_ans;
}
function lowerBound(a, low, high, element)
{
while (low < high)
{
let middle = low +
parseInt((high - low) / 2, 10);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Driver code
let N = 13;
// Function Call
document.write(sumOfPathNodes(N) + "</br>");
// This code is contributed by divyeshrabadiya07
</script>
Producción:
20
Complejidad temporal: O(log N)
Espacio auxiliar: O(log N)