C++ | O(N) efficient solution but ugly code
IntuitionThere are 2 parts to this problem:
Simulate the game and keep track of who received the ball
Find everyone who lost the game and sort them in ascending
# Intuition
There are 2 parts to this problem:
- Simulate the game and keep track of who received the ball
- Find everyone who lost the game and sort them in ascending order

## *unordered_set*
Originally, I thought about using 2 *unordered_set* to keep track of all the players that received the ball and those who did not. That way, I could easily check if a player received the ball for the second time and be able to know when the game should end.

The reason why an *unordered_set* approach is not the most efficient solution for this problem is that there is no practical way to retrieve the players that lost the game and have them in ascending order.

The only method to achieve that would be to iterate the *unordered_set* of players that never received the ball while creating and filling the output vector. However, that alone would not be enough, since *unordered_set*, as the name implies, does not preserve any order. Therefore, to guarantee that the output vector is in ascending order, a sort is required and that takes O(N * log(N)).

I have not tested if such approach would be accepted in this problem, but considering the problem's constraint, it should be perfectly fine.

## *set*
As using an *unordered_set* was out of the question, I wondered how using a *set* instead would make things different.

On one hand, using a *set* avoids having to sort the output vector which means we can avoid an O(N * log(N)) operation. On the other hand, the insert and find operation in a *set* have a O(log(N)) time complexity.

After each game turn, we could end up having to perform a delete operation on the *set* in order to remove a player that never received a ball until that moment. So, in other words, we are still stuck with a time complexity of O(N * log(N)).

In the worst case, a game can have 0 losers, meaning that all the players received the ball once and we had to perform N delete operations on the *set*.

## *vector<bool>*
Neither an *unordered_set* and a *set* allows us to reach the best time complexity for this problem which would be O(N). Then, how can we achieve that?

There were 2 main roadblocks that prevented us from getting that O(N) time complexity:
- Sort the output solution (O(N * log(N)))
- Inefficient insertion, deletion and search operations (O(log(N)))

Knowing that, which data structure can we use to overcome those issues? Thanks to how this problem works, the best data structure that fits these needs and requirements is a *vector*, array or similar.

A *vector* has amortized constant time complexity for its insertion and delete operations. Although, for the solution that I have come up with, we do not need to perform any insertion or deletion operation.

Technically, finding a specific element in a *vector* is an O(N) operation as you would need to traverse the whole *vector*. However, since all the players are numbered from 1 to N, we can map each player's number to a valid vector index position by simply subtracting 1 from the player number and achieve a constant O(1) operation.
- Player 1 = 0 index position in *vector*
- Player N = N - 1 index position in *vector*

This allows us to have a *vector* which pretty much behaves like an *unordered_set*. I am specifically going to use a *vector* that stores *bool* values to indicate if a player has received or not received the ball yet.

# Approach
There are 2 parts to this problem:
- Simulate the game and keep track of who received the ball
    - Create a *vector<bool>* data structure to track the players who have received the ball
    - Create a loop that will continue simulating the game until you get to a player which has already previously received the ball
    - Inside the loop, update the ball's pass distance and set to *true* the player that received the ball on that particular game turn
    - (Optional) Keep track of the number of players that have not received the ball 
- Find everyone who lost the game and sort them in ascending order
    - To know which players lost the game, iterate the *vector<bool>* and check for any player who has its *bool* value set to *false*
    - No need to specifically sort the output in ascending order because by iterating the *vector<bool>* we are already doing so
    - (Optional) If you kept track of the number of players that have not received the ball, you can exit early this *vector<bool>* loop whenever the ouput vector size matches with the number of players that do not have received the ball. This optimization can improve efficiency considerably in the cases where all the game losers are the initial players.

# Complexity
- Time complexity: O(2N) = O(N)
    - O(N) for simulating the game
    - O(N) for creating the output solution

- Space complexity: O(N)
    - O(N) for a helper data structure to keep track of which players have received or not received a ball
    - I do not count the space required to return the problem solution

# Code
```cpp []
#include <vector>
#include <cstdint>

class Solution {
public:
    std::vector<int> circularGameLosers(int n, int k) {
        uint8_t players_ball_counter = 0;
        std::vector<bool> players_who_received_ball = std::vector<bool>(n, false);
        for (
            uint16_t player_index = 0,
                    turn = 1,
                    distance = turn * k;
            
            !players_who_received_ball[player_index];
            
            (
                player_index = (player_index + distance) % n,
                turn++,
                distance = turn * k
            )
        ) {
            players_who_received_ball[player_index] = true;
            players_ball_counter++;
        }

        std::vector<int32_t> players_who_never_received_ball = std::vector<int32_t>(n - players_ball_counter);
        for (
            uint8_t iterator_index = 0,
                    result_index = 0;
            result_index != players_who_never_received_ball.size();
            iterator_index++
        ) {
            if (!players_who_received_ball[iterator_index]) {
                players_who_never_received_ball[result_index] = iterator_index + 1;
                result_index++;
            }
        }
        return players_who_never_received_ball;
    }
};
```
['C++']