Find the Winner of the Circular Game

summary

• The problem is a game where n friends are sitting in a circle and the winner is determined by counting k friends in the clockwise direction, including the starting friend
• The last friend counted leaves the circle and loses the game.

approach

• The approach used in the solution code is to simulate the game by inserting the friends into a circular linked list and then repeatedly removing the last k friends from the list until only one friend is left
• The last remaining friend is the winner.

complexity

• The time complexity of the solution code is O(n * k), where n is the number of friends and k is the number of friends to count
• This is because the code inserts each friend into the list once and then repeatedly removes the last k friends from the list until only one friend is left.

explain

• The solution code first inserts all n friends into a circular linked list using the `insertLast` method
• Then, it repeatedly removes the last k friends from the list using the `removeK` method until only one friend is left
• The last remaining friend is the winner, which is returned by the `findTheWinner` method.

Solution Code:

struct node{
    int val;
    struct node *next;
    struct node *prev;
    node(){
        val = -1;
        next = this;
        prev = this;
    }
};




class Solution {
public:
    node head;
    
    void insertLast(int v){
        node* newNode = new node();
        newNode->val = v;
        newNode->prev = head.prev;
        newNode->next = &head;
        head.prev->next = newNode;
        head.prev = newNode;
    }
    node* removeK(node* ptr, int k){
        for(int i = 0 ; i < k; i++){
            if(ptr->next == &head){
                ptr = ptr->next;
            }
            ptr = ptr->next;
        }
        if (ptr->next == &head){
            ptr = ptr->next;
        }
        node* deleteNode = ptr->next;
        ptr->next = deleteNode->next;
        deleteNode->next->prev = ptr;
        // delete deleteNode;
        return ptr;
    }

    int findTheWinner(int n, int k) {
        for(int i = 1; i <= n; i++){
            insertLast(i);
        }
        node* ptr = &head;
        while(n-- > 1){
            ptr = removeK(ptr, k-1);
            cout << ptr->next->val << endl;
        }
        return head.next->val;
    }
};