Considere una familia especial de Ingenieros y Doctores con las siguientes reglas:
- Todo el mundo tiene dos hijos.
- El primer hijo de un ingeniero es ingeniero y el segundo hijo es médico.
- El primer hijo de un Doctor es Doctor y el segundo hijo es Ingeniero.
- Todas las generaciones de Doctores e Ingenieros comienzan con Ingeniero.
Podemos representar la situación usando el siguiente diagrama:
E
/
E D
/ /
E D D E
/ / / /
E D D E D E E D
Dado el nivel y la posición de una persona en el árbol de antepasados anterior, encuentre la profesión de la persona.
Ejemplos:
Input : level = 4, pos = 2 Output : Doctor Input : level = 3, pos = 4 Output : Engineer
Método 1 (Recursivo)
La idea se basa en el hecho de que la profesión de una persona depende de dos siguientes.
- Profesión de los padres.
- Posición del Node: si la posición de un Node es impar, entonces su profesión es la misma que la de su padre. Else profesión es diferente de su padre.
Encontramos recursivamente la profesión del padre, luego usamos el punto 2 anterior para encontrar la profesión del Node actual.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find profession of a person at
// given level and position.
#include<bits/stdc++.h>
using namespace std;
// Returns 'e' if profession of node at given level
// and position is engineer. Else doctor. The function
// assumes that given position and level have valid values.
char findProffesion(int level, int pos)
{
// Base case
if (level == 1)
return 'e';
// Recursively find parent's profession. If parent
// is a Doctor, this node will be a Doctor if it is
// at odd position and an engineer if at even position
if (findProffesion(level-1, (pos+1)/2) == 'd')
return (pos%2)? 'd' : 'e';
// If parent is an engineer, then current node will be
// an engineer if at add position and doctor if even
// position.
return (pos%2)? 'e' : 'd';
}
// Driver code
int main(void)
{
int level = 4, pos = 2;
(findProffesion(level, pos) == 'e')? cout << "Engineer"
: cout << "Doctor" ;
return 0;
}
Java
// Java program to find
// profession of a person
// at given level and position
import java.io.*;
class GFG
{
// Returns 'e' if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
static char findProffesion(int level,
int pos)
{
// Base case
if (level == 1)
return 'e';
// Recursively find parent's
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if (findProffesion(level - 1,
(pos + 1) / 2) == 'd')
return (pos % 2 > 0) ?
'd' : 'e';
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return (pos % 2 > 0) ?
'e' : 'd';
}
// Driver code
public static void main (String[] args)
{
int level = 4, pos = 2;
if(findProffesion(level,
pos) == 'e')
System.out.println("Engineer");
else
System.out.println("Doctor");
}
}
// This code is contributed
// by anuj_67.
Python3
# python 3 program to find profession of a person at
# given level and position.
# Returns 'e' if profession of node at given level
# and position is engineer. Else doctor. The function
# assumes that given position and level have valid values.
def findProffesion(level, pos):
# Base case
if (level == 1):
return 'e'
# Recursively find parent's profession. If parent
# is a Doctor, this node will be a Doctor if it is
# at odd position and an engineer if at even position
if (findProffesion(level-1, (pos+1)//2) == 'd'):
if (pos%2):
return 'd'
else:
return 'e'
# If parent is an engineer, then current node will be
# an engineer if at add position and doctor if even
# position.
if(pos%2):
return 'e'
else:
return 'd'
# Driver code
if __name__ == '__main__':
level = 3
pos = 4
if(findProffesion(level, pos) == 'e'):
print("Engineer")
else:
print("Doctor")
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find
// profession of a person
// at given level and position
using System;
class GFG
{
// Returns 'e' if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
static char findProffesion(int level,
int pos)
{
// Base case
if (level == 1)
return 'e';
// Recursively find parent's
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if (findProffesion(level - 1,
(pos + 1) / 2) == 'd')
return (pos % 2 > 0) ?
'd' : 'e';
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return (pos % 2 > 0) ?
'e' : 'd';
}
// Driver code
public static void Main ()
{
int level = 4, pos = 2;
if(findProffesion(level,
pos) == 'e')
Console.WriteLine("Engineer");
else
Console.WriteLine("Doctor");
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP program to find profession
// of a person at given level
// and position.
// Returns 'e' if profession of
// node at given level and position
// is engineer. Else doctor. The
// function assumes that given
// position and level have valid values.
function findProffesion($level, $pos)
{
// Base case
if ($level == 1)
return 'e';
// Recursively find parent's
// profession. If parent is
// a Doctor, this node will
// be a doctor if it is at
// odd position and an engineer
// if at even position
if (findProffesion($level - 1,
($pos + 1) / 2) == 'd')
return ($pos % 2) ? 'd' : 'e';
// If parent is an engineer, then
// current node will be an engineer
// if at odd position and doctor
// if even position.
return ($pos % 2) ? 'e' : 'd';
}
// Driver code
$level = 4; $pos = 2;
if((findProffesion($level,
$pos) == 'e') == true)
echo "Engineer";
else
echo "Doctor" ;
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find
// profession of a person
// at given level and position
// Returns 'e' if profession
// of node at given level
// and position is engineer.
// Else doctor. The function
// assumes that given position
// and level have valid values.
function findProffesion(level,
pos)
{
// Base case
if (level == 1)
return 'e';
// Recursively find parent's
// profession. If parent
// is a Doctor, this node
// will be a Doctor if it
// is at odd position and an
// engineer if at even position
if (findProffesion(level - 1,
(pos + 1) / 2) == 'd')
return (pos % 2 > 0) ?
'd' : 'e';
// If parent is an engineer,
// then current node will be
// an engineer if at add
// position and doctor if even
// position.
return (pos % 2 > 0) ?
'e' : 'd';
}
// Driver Code
let level = 4, pos = 2;
if(findProffesion(level,
pos) == 'e')
document.write("Engineer");
else
document.write("Doctor");
</script>
Producción :
Doctor
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Método 2 (usando operadores bit a bit)
Level 1: E Level 2: ED Level 3: EDDE Level 4: EDDEDEED Level 5: EDDEDEEDDEEDEDDE
La entrada de nivel no es necesaria (si ignoramos el límite máximo de posición) porque los primeros elementos son los mismos.
El resultado se basa en el conteo de 1 en representación binaria de la posición menos uno. Si la cuenta de 1 es par, entonces el resultado es Ingeniero, de lo contrario, Doctor.
Y, por supuesto, el límite de posición es 2^(Nivel-1)
C++
// C++ program to find profession of a person at
// given level and position.
#include<bits/stdc++.h>
using namespace std;
/* Function to get no of set bits in binary
representation of passed binary no. */
int countSetBits(int n)
{
int count = 0;
while (n)
{
n &= (n-1) ;
count++;
}
return count;
}
// Returns 'e' if profession of node at given level
// and position is engineer. Else doctor. The function
// assumes that given position and level have valid values.
char findProffesion(int level, int pos)
{
// Count set bits in 'pos-1'
int c = countSetBits(pos-1);
// If set bit count is odd, then doctor, else engineer
return (c%2)? 'd' : 'e';
}
// Driver code
int main(void)
{
int level = 3, pos = 4;
(findProffesion(level, pos) == 'e')? cout << "Engineer"
: cout << "Doctor" ;
return 0;
}
Java
// Java program to find profession of a person at
// given level and position.
class GFG{
/* Function to get no of set bits in binary
representation of passed binary no. */
static int countSetBits(int n)
{
int count = 0;
while (n!=0)
{
n &= (n-1) ;
count++;
}
return count;
}
// Returns 'e' if profession of node at given level
// and position is engineer. Else doctor. The function
// assumes that given position and level have valid values.
static char findProffesion(int level, int pos)
{
// Count set bits in 'pos-1'
int c = countSetBits(pos-1);
// If set bit count is odd, then doctor, else engineer
return (c%2 !=0)? 'd' : 'e';
}
// Driver code
public static void main(String [] args)
{
int level = 3, pos = 4;
String prof = (findProffesion(level, pos) == 'e')? "Engineer"
: "Doctor" ;
System.out.print(prof);
}
}
Python3
# Python3 program to find profession of a person at
# given level and position.
""" Function to get no of set bits in binary
representation of passed binary no. """
def countSetBits(n):
count = 0
while n > 0:
n &= (n-1)
count+=1
return count
# Returns 'e' if profession of node at given level
# and position is engineer. Else doctor. The function
# assumes that given position and level have valid values.
def findProffesion(level, pos):
# Count set bits in 'pos-1'
c = countSetBits(pos-1)
# If set bit count is odd, then doctor, else engineer
if c%2 == 0:
return 'e'
else:
return 'd'
level, pos = 3, 4
if findProffesion(level, pos) == 'e':
print("Engineer")
else:
print("Doctor")
# This code is contributed by divyeshrabadiya07.
C#
using System;
// c# program to find profession of a person at
// given level and position.
public class GFG
{
/* Function to get no of set bits in binary
representation of passed binary no. */
public static int countSetBits(int n)
{
int count = 0;
while (n != 0)
{
n &= (n - 1);
count++;
}
return count;
}
// Returns 'e' if profession of node at given level
// and position is engineer. Else doctor. The function
// assumes that given position and level have valid values.
public static char findProffesion(int level, int pos)
{
// Count set bits in 'pos-1'
int c = countSetBits(pos - 1);
// If set bit count is odd, then doctor, else engineer
return (c % 2 != 0)? 'd' : 'e';
}
// Driver code
public static void Main(string[] args)
{
int level = 3, pos = 4;
string prof = (findProffesion(level, pos) == 'e')? "Engineer" : "Doctor";
Console.Write(prof);
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to find profession
// of a person at given level and position.
// Function to get no of set
// bits in binary representation
// of passed binary no.
function countSetBits($n)
{
$count = 0;
while ($n)
{
$n &= ($n - 1) ;
$count++;
}
return $count;
}
// Returns 'e' if profession of
// node at given level and position
// is engineer. Else doctor. The
// function assumes that given
// position and level have valid values.
function findProffesion($level, $pos)
{
// Count set bits in 'pos-1'
$c = countSetBits($pos - 1);
// If set bit count is odd,
// then doctor, else engineer
return ($c % 2) ? 'd' : 'e';
}
// Driver Code
$level = 3;
$pos = 4;
if((findProffesion($level,
$pos) == 'e') == true)
echo "Engineer \n";
else
echo "Doctor \n";
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find
// profession of a person at
// given level and position.
/* Function to get no of set bits in binary
representation of passed binary no. */
function countSetBits(n)
{
let count = 0;
while (n != 0)
{
n &= (n - 1);
count++;
}
return count;
}
// Returns 'e' if profession of node at given level
// and position is engineer. Else doctor.
// The function assumes that given position and
// level have valid values.
function findProffesion(level, pos)
{
// Count set bits in 'pos-1'
let c = countSetBits(pos - 1);
// If set bit count is odd, then doctor,
// else engineer
return (c % 2 != 0)? 'd' : 'e';
}
let level = 3, pos = 4;
let prof = (findProffesion(level, pos) == 'e')?
"Engineer" : "Doctor";
document.write(prof);
</script>
Producción :
Engineer
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Gracias a Furkan Uslu por sugerir este método.
Este artículo es una contribución de Harsh Parikh . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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