There are `n`

friends that are playing a game. The friends are sitting in a circle and are numbered from `1`

to `n`

in **clockwise order**. More formally, moving clockwise from the `i`

friend brings you to the ^{th}`(i+1)`

friend for ^{th}`1 <= i < n`

, and moving clockwise from the `n`

friend brings you to the ^{th}`1`

friend.^{st}

The rules of the game are as follows:

**Start**at the`1`

friend.^{st}- Count the next
`k`

friends in the clockwise direction**including**the friend you started at. The counting wraps around the circle and may count some friends more than once. - The last friend you counted leaves the circle and loses the game.
- If there is still more than one friend in the circle, go back to step
`2`

**starting**from the friend**immediately clockwise**of the friend who just lost and repeat. - Else, the last friend in the circle wins the game.

Given the number of friends, `n`

, and an integer `k`

, return *the winner of the game*.

**Example 1:**

Input:n = 5, k = 2Output:3Explanation:Here are the steps of the game: 1) Start at friend 1. 2) Count 2 friends clockwise, which are friends 1 and 2. 3) Friend 2 leaves the circle. Next start is friend 3. 4) Count 2 friends clockwise, which are friends 3 and 4. 5) Friend 4 leaves the circle. Next start is friend 5. 6) Count 2 friends clockwise, which are friends 5 and 1. 7) Friend 1 leaves the circle. Next start is friend 3. 8) Count 2 friends clockwise, which are friends 3 and 5. 9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

**Example 2:**

Input:n = 6, k = 5Output:1Explanation:The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.

**Constraints:**

`1 <= k <= n <= 500`

```
struct Solution;
impl Solution {
fn find_the_winner(n: i32, k: i32) -> i32 {
let mut friends = vec![];
for i in 1..=n {
friends.push(i);
}
let mut i = 0;
loop {
let m = friends.len();
if m == 1 {
break;
}
i = (i as i32 + k - 1) as usize % m;
friends.remove(i);
if i == m - 1 {
i = 0;
}
}
friends[0]
}
}
#[test]
fn test() {
let n = 5;
let k = 2;
let res = 3;
assert_eq!(Solution::find_the_winner(n, k), res);
let n = 6;
let k = 5;
let res = 1;
assert_eq!(Solution::find_the_winner(n, k), res);
}
```