Dado un árbol binario infinitamente largo que tiene un patrón como el siguiente:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
......................
También dada una array arr de tamaño N y un número K . La tarea es colorear todos los subárboles del Node arr[i] con el color i (1 <= i <= N) uno tras otro. Encuentre el color del Node K después de colorear todos los subárboles.
Nota: – Inicialmente, todos los Nodes tienen el color 0.
Entrada: arr[] = {3, 2, 1, 3}, K = 7
Salida: 4
Explicación:
después de aplicar el color 1 al subárbol en el Node 3, el Node 7 contiene el color 1.
Después de aplicar el color 2 al subárbol en el Node 2, el Node 7 contiene el color 1.
Después de aplicar el color 3 al subárbol del Node 1, el Node 7 contiene el color 3.
Después de aplicar el color 4 al subárbol del Node 3, el Node 7 contiene el color 4.Entrada: arr[] = {3, 2, 1, 3}, K = 4
Salida: 3
Explicación:
después de aplicar el color 1 al subárbol en el Node 3, el Node 4 contiene el color 0.
Después de aplicar el color 2 al subárbol en el Node 2, el Node 4 contiene el color 2.
Después de aplicar el color 3 al subárbol del Node 1, el Node 4 contiene el color 3.
Después de aplicar el color 4 al subárbol del Node 3, el Node 4 contiene el color 3.
Un enfoque ingenuo es para cada índice i (1 <= i <= N) actualizar el color de todos los Nodes en un subárbol hasta que el nivel de los Nodes sea menor que el nivel del Node K dado. Después de N tales operaciones imprimen el color del Node K.
Un enfoque eficiente es usar hash
- Primero, inserte todos los Nodes con sus respectivos colores en un mapa (en caso de que un Node tenga más de un color, mantenga uno con el número máximo de colores).
- Encuentre todos los ancestros del Node k dado y genere el color que tenga un número máximo. (Si el Node actual es x , entonces (x-1)/2 o x/2 son sus ancestros)
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find color of the node
#include <bits/stdc++.h>
using namespace std;
// Function to find color of the node
int findColor(map<int, int> mapWithColor, int query)
{
// Maximum is to store maximum color
int maximum = 0;
// Loop to check all the parent
// values to get maximum color
while (query >= 1) {
// Find the number into map and get maximum color
if (mapWithColor.find(query) != mapWithColor.end())
{
// Take the maximum color and
// assign into maximum variable
maximum = max(maximum, mapWithColor[query]);
}
// Find parent index
if (query % 2 == 1)
query = (query - 1) / 2;
else
query = query / 2;
}
// Return maximum color
return maximum;
}
// Function to build hash map with color
map<int, int> buildMapWithColor(int arr[], int n)
{
// To store color of each node
map<int, int> mapWithColor;
// For each number add a color number
for (int i = 0; i < n; i++) {
// Assigning color
mapWithColor[arr[i]] = i + 1;
}
// Return hash map
return mapWithColor;
}
// Driver code
int main()
{
int arr[] = { 3, 2, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 7;
// Build mapWithColor
map<int, int> mapWithColor = buildMapWithColor(arr, n);
// Print the maximum color
cout << findColor(mapWithColor, k);
return 0;
}
Java
// JAVA program to find color of the node
import java.util.*;
class GFG
{
// Function to find color of the node
static int findColor(HashMap<Integer, Integer> mapWithColor, int query)
{
// Maximum is to store maximum color
int maximum = 0;
// Loop to check all the parent
// values to get maximum color
while (query >= 1)
{
// Find the number into map and get maximum color
if (mapWithColor.containsKey(query))
{
// Take the maximum color and
// assign into maximum variable
maximum = Math.max(maximum, mapWithColor.get(query));
}
// Find parent index
if (query % 2 == 1)
query = (query - 1) / 2;
else
query = query / 2;
}
// Return maximum color
return maximum;
}
// Function to build hash map with color
static HashMap<Integer, Integer> buildMapWithColor(int arr[], int n)
{
// To store color of each node
HashMap<Integer, Integer> mapWithColor = new HashMap<Integer, Integer>();
// For each number add a color number
for (int i = 0; i < n; i++)
{
// Assigning color
mapWithColor.put(arr[i], i + 1);
}
// Return hash map
return mapWithColor;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1, 3 };
int n = arr.length;
int k = 7;
// Build mapWithColor
HashMap<Integer, Integer> mapWithColor = buildMapWithColor(arr, n);
// Print the maximum color
System.out.print(findColor(mapWithColor, k));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 code program to find color of the node
# Function to find color of the node
def findColor(mapWithColor, query):
# Maximum is to store maximum color
maximum = 0
# Loop to check all the parent
# values to get maximum color
while (query >= 1):
# Find the number into map and get maximum color
if (query) in mapWithColor.keys():
# Take the maximum color and
# assign into maximum variable
maximum = max(maximum, mapWithColor[query])
# Find parent index
if (query % 2 == 1):
query = (query - 1) // 2
else:
query = query // 2
# Return maximum color
return maximum
# Function to build hash map with color
def buildMapWithColor(arr, n):
# To store color of each node
mapWithColor={}
# For each number add a color number
for i in range(n):
# Assigning color
mapWithColor[arr[i]] = i + 1
# Return hash map
return mapWithColor
# Driver code
arr = [3, 2, 1, 3]
n = len(arr)
k = 7
# Build mapWithColor
mapWithColor = buildMapWithColor(arr, n)
# Print the maximum color
print(findColor(mapWithColor, k))
# This code is contributed by mohit kumar 29
C#
// C# program to find color of the node
using System;
using System.Collections.Generic;
class GFG
{
// Function to find color of the node
static int findColor(Dictionary<int, int> mapWithColor, int query)
{
// Maximum is to store maximum color
int maximum = 0;
// Loop to check all the parent
// values to get maximum color
while (query >= 1)
{
// Find the number into map and get maximum color
if (mapWithColor.ContainsKey(query))
{
// Take the maximum color and
// assign into maximum variable
maximum = Math.Max(maximum, mapWithColor[query]);
}
// Find parent index
if (query % 2 == 1)
query = (query - 1) / 2;
else
query = query / 2;
}
// Return maximum color
return maximum;
}
// Function to build hash map with color
static Dictionary<int, int> buildMapWithColor(int []arr, int n)
{
// To store color of each node
Dictionary<int, int> mapWithColor = new Dictionary<int, int>();
// For each number add a color number
for (int i = 0; i < n; i++)
{
// Assigning color
if(mapWithColor.ContainsKey(arr[i]))
mapWithColor[arr[i]] = i + 1;
else
mapWithColor.Add(arr[i], i + 1);
}
// Return hash map
return mapWithColor;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 3, 2, 1, 3 };
int n = arr.Length;
int k = 7;
// Build mapWithColor
Dictionary<int, int> mapWithColor = buildMapWithColor(arr, n);
// Print the maximum color
Console.Write(findColor(mapWithColor, k));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find color of the node
// Function to find color of the node
function findColor(mapWithColor, query)
{
// Maximum is to store maximum color
let maximum = 0;
// Loop to check all the parent
// values to get maximum color
while (query >= 1)
{
// Find the number into map and get maximum color
if (mapWithColor.has(query))
{
// Take the maximum color and
// assign into maximum variable
maximum = Math.max(maximum, mapWithColor.get(query));
}
// Find parent index
if (query % 2 == 1)
query = (query - 1) / 2;
else
query = query / 2;
}
// Return maximum color
return maximum;
}
// Function to build hash map with color
function buildMapWithColor(arr, n)
{
// To store color of each node
let mapWithColor = new Map();
// For each number add a color number
for (let i = 0; i < n; i++)
{
// Assigning color
mapWithColor.set(arr[i], i + 1);
}
// Return hash map
return mapWithColor;
}
// Driver code
let arr = [ 3, 2, 1, 3 ];
let n = arr.length;
let k = 7;
// Build mapWithColor
let mapWithColor = buildMapWithColor(arr, n);
// Print the maximum color
document.write(findColor(mapWithColor, k));
// This code is contributed by susmitakundugoaldanga.
</script>
4
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA