Encuentre los últimos 2 sobrevivientes en N personas de pie en un círculo después de matar al lado del vecino inmediato

Posted on by Rudeus Greyrat

Dado un número entero N que representa a N personas de pie en un círculo, la tarea es encontrar las últimas 2 personas que quedan cuando una persona mata a su vecino inmediato en el sentido de las agujas del reloj.

Ejemplos:  

Entrada: N = 5 
Salida: 1 4 
Explicación: 
Inicialmente: 1 2 3 4 5 
=> 1 mata 3 
En pie: 1 2 4 5
=> 2 mata 5 
En pie: 1 2 4
=> 4 mata 2 
Posición final: 1 4

Entrada: N = 2 
Salida: 1 2 

Enfoque ingenuo: un enfoque simple es mantener una array bool de tamaño N para realizar un seguimiento de si una persona está viva o no.  

  • Inicialmente, la array booleana será verdadera para todas las personas.
  • Mantenga dos punteros , uno en la persona viva actual y el segundo para almacenar la persona actual anterior.
  • Una vez encontrado un segundo vecino vivo de la persona actual, cambie su valor booleano a falso.
  • Luego, nuevamente, el actual se actualiza al siguiente vivo del anterior.
  • Este proceso continuará hasta que sobrevivan las dos últimas personas.

Tiempo Complejidad: O(N 2 )  
Espacio Auxiliar: O(N)

Enfoque eficiente: un enfoque eficiente es eliminar a la persona, si está muerta, de la estructura de datos para que no se vuelva a atravesar.

  • Después de una sola ronda completa, habrá solo N/2 personas, como máximo.
  • Luego en la siguiente ronda quedará con N/4 persona y así sucesivamente hasta que un número de personas vivas se convierta en 2.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Node for a Linked List
struct Node {
    int val;
    struct Node* next;
 
    Node(int _val)
    {
        val = _val;
        next = NULL;
    }
};
 
// Function to find the last 2 survivors
void getLastTwoPerson(int n)
{
    // Total is the count
    // of alive people
    int total = n;
    struct Node* head = new Node(1);
    struct Node* temp = head;
 
    // Initiating the list of n people
    for (int i = 2; i <= n; i++) {
        temp->next = new Node(i);
        temp = temp->next;
    }
 
    temp->next = head;
    temp = head;
 
    struct Node* del;
 
    // Total != 2 is terminating
    // condition because
    // at last only two-person
    // will remain alive
    while (total != 2) {
 
        // Del represent next person
        // to be deleted or killed
        del = temp->next->next;
        temp->next->next
            = temp->next->next->next;
        temp = temp->next;
        free(del);
        total -= 1;
    }
 
    // Last two person to
    // survive (in any order)
    cout << temp->val << " "
         << temp->next->val;
}
 
// Driver code
int main()
{
    int n = 2;
 
    getLastTwoPerson(n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG{
 
// Node for a Linked List
static class Node
{
    int val;
    Node next;
 
    Node(int _val)
    {
        val = _val;
        next = null;
    }
};
 
// Function to find the last 2 survivors
static void getLastTwoPerson(int n)
{
     
    // Total is the count
    // of alive people
    int total = n;
    Node head = new Node(1);
    Node temp = head;
 
    // Initiating the list of n people
    for(int i = 2; i <= n; i++)
    {
        temp.next = new Node(i);
        temp = temp.next;
    }
 
    temp.next = head;
    temp = head;
 
    Node del;
 
    // Total != 2 is terminating
    // condition because
    // at last only two-person
    // will remain alive
    while (total != 2)
    {
 
        // Del represent next person
        // to be deleted or killed
        del = temp.next.next;
        temp.next.next = temp.next.next.next;
        temp = temp.next;
        del = null;
         
        System.gc();
        total -= 1;
    }
 
    // Last two person to
    // survive (in any order)
    System.out.print(temp.val + " " +
                     temp.next.val);
}
 
// Driver code
public static void main(String[] args)
{
    int n = 2;
 
    getLastTwoPerson(n);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the approach
 
# Node for a Linked List
class newNode:
     
    def __init__(self, val):
         
        self.val = val
        self.next = None
 
# Function to find the last 2 survivors
def getLastTwoPerson(n):
     
    # Total is the count
    # of alive people
    total = n
    head = newNode(1)
    temp = head
 
    # Initiating the list of n people
    for i in range(2, n + 1, 1):
        temp.next = newNode(i)
        temp = temp.next
 
    temp.next = head
    temp = head
 
    de = None
 
    # Total != 2 is terminating
    # condition because
    # at last only two-person
    # will remain alive
    while (total != 2):
         
        # de represent next person
        # to be deleted or killed
        de = temp.next.next
        temp.next.next = temp.next.next.next
        temp = temp.next
        del de
        total -= 1
 
    # Last two person to
    # survive (in any order)
    print(temp.val, temp.next.val)
 
# Driver code
if __name__ == '__main__':
     
    n = 2
     
    getLastTwoPerson(n)
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# implementation of the approach
using System;
 
class GFG{
 
// Node for a Linked List
class Node
{
    public int val;
    public Node next;
 
    public Node(int _val)
    {
        val = _val;
        next = null;
    }
};
 
// Function to find the last 2 survivors
static void getLastTwoPerson(int n)
{
     
    // Total is the count
    // of alive people
    int total = n;
    Node head = new Node(1);
    Node temp = head;
 
    // Initiating the list of n people
    for(int i = 2; i <= n; i++)
    {
        temp.next = new Node(i);
        temp = temp.next;
    }
 
    temp.next = head;
    temp = head;
 
    Node del;
 
    // Total != 2 is terminating
    // condition because
    // at last only two-person
    // will remain alive
    while (total != 2)
    {
 
        // Del represent next person
        // to be deleted or killed
        del = temp.next.next;
        temp.next.next = temp.next.next.next;
        temp = temp.next;
        del = null;
         
        total -= 1;
    }
 
    // Last two person to
    // survive (in any order)
    Console.Write(temp.val + " " +
                  temp.next.val);
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 2;
 
    getLastTwoPerson(n);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript implementation of the approach
 
// Node for a Linked List
class Node {
 
    constructor(val)
    {
        this.val = val;
        this.next = null;
    }
};
 
// Function to find the last 2 survivors
function getLastTwoPerson(n)
{
    // Total is the count
    // of alive people
    var total = n;
    var head = new Node(1);
    var temp = head;
 
    // Initiating the list of n people
    for (var i = 2; i <= n; i++) {
        temp.next = new Node(i);
        temp = temp.next;
    }
 
    temp.next = head;
    temp = head;
 
    var del;
 
    // Total != 2 is terminating
    // condition because
    // at last only two-person
    // will remain alive
    while (total != 2) {
 
        // Del represent next person
        // to be deleted or killed
        del = temp.next.next;
        temp.next.next
            = temp.next.next.next;
        temp = temp.next;
        total -= 1;
    }
 
    // Last two person to
    // survive (in any order)
    document.write( temp.val + " "
         + temp.next.val);
}
 
// Driver code
var n = 2;
getLastTwoPerson(n);
 
// This code is contributed by noob2000.
</script>
Producción: 

1 2

 

Complejidad de tiempo: O(N*log N)  
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por souravrawat191 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *