Find last 2 survivors in N persons standing in a circle after killing next to immediate neighbour
Given an integer N representing N persons standing in a circle, the task is to find the last 2 persons remaining when a person kills their next to the immediate neighbor in a clockwise direction.
Examples:
Input: N = 5
Output: 1 4
Explanation:
Initially: 1 2 3 4 5
=> 1 kills 3
Standing: 1 2 4 5
=> 2 kills 5
Standing: 1 2 4
=> 4 kills 2
Final Standing: 1 4Input: N = 2
Output: 1 2
Naive Approach: A simple approach is to keep a bool array of size N to keep track of whether a person is alive or not.
- Initially, the boolean array will be true for all persons.
- Keep two pointers, one at the current alive person and second to store previous current person.
- Once found a second alive neighbour from the current person, change its boolean value to false.
- Then again current is updated to next alive from previous.
- This process will continue till last two persons survive.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: An efficient approach is to remove the person, if dead, from the data structure so that it is not traversed again.
- After one complete round only, there will be only N/2 person, at max.
- Then in the next round it will be left with N/4 person and so on until a number of alive people become 2.
Below is the implementation of the above approach:
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> |
1 2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)