Dadas n personas paradas en un círculo donde el primero tiene una espada, encuentre a la persona más afortunada en el círculo, si, del primer soldado que tiene una espada, cada uno tiene que matar al siguiente soldado y entregar la espada al siguiente soldado, a su vez, el el soldado matará al soldado adyacente y le entregará la espada al próximo soldado de modo que un soldado permanezca en esta guerra que no sea asesinado por nadie.
Prerrequisito: Rompecabezas 81 | Puzzle de 100 personas en círculo con una pistola
Ejemplos:
Entrada: 5
Salida: 3
Explicación:
N = 5
Soldado 1 2 3 4 5 (5 soldados)
En el primer intento 1 3 5 (permanece) como 2 y 4 asesinados por 1 y 3.
En el segundo intento 3 como 5 asesinados 1 y 3. matar a 5 soldado 3 sigue vivo.Entrada: 100
Salida: 73
Explicación:
N = 10
Soldados 1 2 3 4 5 6 7 8 9 10 (10 soldados)
En el primero 1 3 5 7 9 como 2 4 6 8 10 fueron asesinados por 1 3 5 7 y 9.
En segundo 1 5 9 como 9 matan a 1 ya su vez 5 matan al noveno soldado.
En tercero 5 5to soldados siguen vivos
Enfoque: La idea es utilizar una lista enlazada circular . Se hace una lista enlazada circular basada en un número de soldados N. Como regla general, debe matar a su soldado adyacente y entregar la espada al siguiente soldado, quien a su vez mata a su soldado adyacente y entrega la espada al siguiente soldado. . Entonces, en la lista enlazada circular, el soldado adyacente muere y el soldado restante lucha entre sí de forma circular y sobrevive un solo soldado que no es asesinado por nadie.
C++
// C++ code to find the luckiest person
#include <bits/stdc++.h>
using namespace std;
// Node structure
struct Node {
int data;
struct Node* next;
};
Node *newNode(int data)
{
Node *node = new Node;
node->data = data;
node->next = NULL;
return node;
}
// Function to find the luckiest person
int alivesol(int Num)
{
if (Num == 1)
return 1;
// Create a single node circular
// linked list.
Node *last = newNode(1);
last->next = last;
for (int i = 2; i <= Num; i++) {
Node *temp = newNode(i);
temp->next = last->next;
last->next = temp;
last = temp;
}
// Starting from first soldier.
Node *curr = last->next;
// condition for evaluating the existence
// of single soldier who is not killed.
Node *temp;
while (curr->next != curr) {
temp = curr;
curr = curr->next;
temp->next = curr->next;
// deleting soldier from the circular
// list who is killed in the fight.
delete curr;
temp = temp->next;
curr = temp;
}
// Returning the Luckiest soldier who
// remains alive.
int res = temp->data;
delete temp;
return res;
}
// Driver code
int main()
{
int N = 100;
cout << alivesol(N) << endl;
return 0;
}
Java
// Java code to find the luckiest person
class GFG
{
// Node structure
static class Node
{
int data;
Node next;
};
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.next = null;
return node;
}
// Function to find the luckiest person
static int alivesol(int Num)
{
if (Num == 1)
return 1;
// Create a single node circular
// linked list.
Node last = newNode(1);
last.next = last;
for (int i = 2; i <= Num; i++)
{
Node temp = newNode(i);
temp.next = last.next;
last.next = temp;
last = temp;
}
// Starting from first soldier.
Node curr = last.next;
// condition for evaluating the existence
// of single soldier who is not killed.
Node temp = new Node();
while (curr.next != curr)
{
temp = curr;
curr = curr.next;
temp.next = curr.next;
// deleting soldier from the circular
// list who is killed in the fight.
temp = temp.next;
curr = temp;
}
// Returning the Luckiest soldier who
// remains alive.
int res = temp.data;
return res;
}
// Driver code
public static void main(String args[])
{
int N = 100;
System.out.println( alivesol(N) );
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 code to find the luckiest person # Node structure class Node: def __init__(self, data): self.data = data self.next = None def newNode(data): node = Node(data) return node # Function to find the luckiest person def alivesol( Num): if (Num == 1): return 1; # Create a single node circular # linked list. last = newNode(1); last.next = last; for i in range(2, Num + 1): temp = newNode(i); temp.next = last.next; last.next = temp; last = temp; # Starting from first soldier. curr = last.next; # condition for evaluating the existence # of single soldier who is not killed. temp = None while (curr.next != curr): temp = curr; curr = curr.next; temp.next = curr.next; # deleting soldier from the circular # list who is killed in the fight. del curr; temp = temp.next; curr = temp; # Returning the Luckiest soldier who # remains alive. res = temp.data; del temp; return res; # Driver code if __name__=='__main__': N = 100; print(alivesol(N)) # This code is contributed by rutvik_56
C#
// C# code to find the luckiest person
using System;
class GFG
{
// Node structure
public class Node
{
public int data;
public Node next;
};
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.next = null;
return node;
}
// Function to find the luckiest person
static int alivesol(int Num)
{
if (Num == 1)
return 1;
// Create a single node circular
// linked list.
Node last = newNode(1);
last.next = last;
for (int i = 2; i <= Num; i++)
{
Node tem = newNode(i);
tem.next = last.next;
last.next = tem;
last = tem;
}
// Starting from first soldier.
Node curr = last.next;
// condition for evaluating the existence
// of single soldier who is not killed.
Node tem1 = new Node();
while (curr.next != curr)
{
tem1 = curr;
curr = curr.next;
tem1.next = curr.next;
// deleting soldier from the circular
// list who is killed in the fight.
tem1 = tem1.next;
curr = tem1;
}
// Returning the Luckiest soldier who
// remains alive.
int res = tem1.data;
return res;
}
// Driver code
public static void Main(String []args)
{
int N = 100;
Console.WriteLine( alivesol(N) );
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript code to find the luckiest person
// Node structure
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
function newNode(data)
{
var node = new Node();
node.data = data;
node.next = null;
return node;
}
// Function to find the luckiest person
function alivesol(Num)
{
if (Num == 1)
return 1;
// Create a single node circular
// linked list.
var last = newNode(1);
last.next = last;
for(var i = 2; i <= Num; i++)
{
var tem = newNode(i);
tem.next = last.next;
last.next = tem;
last = tem;
}
// Starting from first soldier.
var curr = last.next;
// Condition for evaluating the existence
// of single soldier who is not killed.
var tem1 = new Node();
while (curr.next != curr)
{
tem1 = curr;
curr = curr.next;
tem1.next = curr.next;
// Deleting soldier from the circular
// list who is killed in the fight.
tem1 = tem1.next;
curr = tem1;
}
// Returning the Luckiest soldier who
// remains alive.
var res = tem1.data;
return res;
}
// Driver code
var N = 100;
document.write(alivesol(N) + "<br>");
// This code is contributed by rdtank
</script>
73
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(n), ya que estamos usando espacio extra para la lista enlazada. Donde n es el número de Nodes en la lista enlazada.
Publicación traducida automáticamente
Artículo escrito por AnupGaurav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA