bowang0911/leetcode huggingface dataset:
Design Snake Game

Design a [Snake game](https://en.wikipedia.org/wiki/Snake_(video_game)) that is played on a device with screen size `height x width`. [Play the game online](http://patorjk.com/games/snake/) if you are not familiar with the game.

The snake is initially positioned at the top left corner `(0, 0)` with a length of `1` unit.

You are given an array `food` where `food[i] = (ri, ci)` is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by `1`.

Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.

When a piece of food appears on the screen, it is **guaranteed** that it will not appear on a block occupied by the snake.

The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies **after** moving (i.e. a snake of length 4 cannot run into itself).

Implement the `SnakeGame` class:

*   `SnakeGame(int width, int height, int[][] food)` Initializes the object with a screen of size `height x width` and the positions of the `food`.
*   `int move(String direction)` Returns the score of the game after applying one `direction` move by the snake. If the game is over, return `-1`.

**Example 1:**

**Input**
\[ "SnakeGame ",  "move ",  "move ",  "move ",  "move ",  "move ",  "move "\]
\[\[3, 2, \[\[1, 2\], \[0, 1\]\]\], \[ "R "\], \[ "D "\], \[ "R "\], \[ "U "\], \[ "L "\], \[ "U "\]\]
**Output**
\[null, 0, 0, 1, 1, 2, -1\]

**Explanation**
SnakeGame snakeGame = new SnakeGame(3, 2, \[\[1, 2\], \[0, 1\]\]);
snakeGame.move( "R "); // return 0
snakeGame.move( "D "); // return 0
snakeGame.move( "R "); // return 1, snake eats the first piece of food. The second piece of food appears at (0, 1).
snakeGame.move( "U "); // return 1
snakeGame.move( "L "); // return 2, snake eats the second food. No more food appears.
snakeGame.move( "U "); // return -1, game over because snake collides with border

**Constraints:**

*   `1 <= width, height <= 104`
*   `1 <= food.length <= 50`
*   `food[i].length == 2`
*   `0 <= ri < height`
*   `0 <= ci < width`
*   `direction.length == 1`
*   `direction` is `'U'`, `'D'`, `'L'`, or `'R'`.
*   At most `104` calls will be made to `move`.
Russian Doll Envelopes

You are given a 2D array of integers `envelopes` where `envelopes[i] = [wi, hi]` represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return _the maximum number of envelopes you can Russian doll (i.e., put one inside the other)_.

**Note:** You cannot rotate an envelope.

**Example 1:**

**Input:** envelopes = \[\[5,4\],\[6,4\],\[6,7\],\[2,3\]\]
**Output:** 3
**Explanation:** The maximum number of envelopes you can Russian doll is `3` (\[2,3\] => \[5,4\] => \[6,7\]).

**Example 2:**

**Input:** envelopes = \[\[1,1\],\[1,1\],\[1,1\]\]
**Output:** 1

**Constraints:**

*   `1 <= envelopes.length <= 105`
*   `envelopes[i].length == 2`
*   `1 <= wi, hi <= 105`
Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the `10` most recent tweets in the user's news feed.

Implement the `Twitter` class:

*   `Twitter()` Initializes your twitter object.
*   `void postTweet(int userId, int tweetId)` Composes a new tweet with ID `tweetId` by the user `userId`. Each call to this function will be made with a unique `tweetId`.
*   `List getNewsFeed(int userId)` Retrieves the `10` most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be **ordered from most recent to least recent**.
*   `void follow(int followerId, int followeeId)` The user with ID `followerId` started following the user with ID `followeeId`.
*   `void unfollow(int followerId, int followeeId)` The user with ID `followerId` started unfollowing the user with ID `followeeId`.

**Example 1:**

**Input**
\[ "Twitter ",  "postTweet ",  "getNewsFeed ",  "follow ",  "postTweet ",  "getNewsFeed ",  "unfollow ",  "getNewsFeed "\]
\[\[\], \[1, 5\], \[1\], \[1, 2\], \[2, 6\], \[1\], \[1, 2\], \[1\]\]
**Output**
\[null, null, \[5\], null, null, \[6, 5\], null, \[5\]\]

**Explanation**
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> \[5\]. return \[5\]
twitter.follow(1, 2);    // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 2 tweet ids -> \[6, 5\]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2);  // User 1 unfollows user 2.
twitter.getNewsFeed(1);  // User 1's news feed should return a list with 1 tweet id -> \[5\], since user 1 is no longer following user 2.

**Constraints:**

*   `1 <= userId, followerId, followeeId <= 500`
*   `0 <= tweetId <= 104`
*   All the tweets have **unique** IDs.
*   At most `3 * 104` calls will be made to `postTweet`, `getNewsFeed`, `follow`, and `unfollow`.
Line Reflection

Given `n` points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically.

In other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points' set is the same as the reflected ones.

**Note** that there can be repeated points.

**Example 1:**

**Input:** points = \[\[1,1\],\[-1,1\]\]
**Output:** true
**Explanation:** We can choose the line x = 0.

**Example 2:**

**Input:** points = \[\[1,1\],\[-1,-1\]\]
**Output:** false
**Explanation:** We can't choose a line.

**Constraints:**

*   `n == points.length`
*   `1 <= n <= 104`
*   `-108 <= points[i][j] <= 108`

**Follow up:** Could you do better than `O(n2)`?
Count Numbers with Unique Digits

Given an integer `n`, return the count of all numbers with unique digits, `x`, where `0 <= x < 10n`.

**Example 1:**

**Input:** n = 2
**Output:** 91
**Explanation:** The answer should be the total numbers in the range of 0 <= x < 100, excluding 11,22,33,44,55,66,77,88,99

**Example 2:**

**Input:** n = 0
**Output:** 1

**Constraints:**

*   `0 <= n <= 8`
Rearrange String k Distance Apart

Given a string `s` and an integer `k`, rearrange `s` such that the same characters are **at least** distance `k` from each other. If it is not possible to rearrange the string, return an empty string `" "`.

**Example 1:**

**Input:** s =  "aabbcc ", k = 3
**Output:**  "abcabc "
**Explanation:** The same letters are at least a distance of 3 from each other.

**Example 2:**

**Input:** s =  "aaabc ", k = 3
**Output:**  " "
**Explanation:** It is not possible to rearrange the string.

**Example 3:**

**Input:** s =  "aaadbbcc ", k = 2
**Output:**  "abacabcd "
**Explanation:** The same letters are at least a distance of 2 from each other.

**Constraints:**

*   `1 <= s.length <= 3 * 105`
*   `s` consists of only lowercase English letters.
*   `0 <= k <= s.length`
Logger Rate Limiter

Design a logger system that receives a stream of messages along with their timestamps. Each **unique** message should only be printed **at most every 10 seconds** (i.e. a message printed at timestamp `t` will prevent other identical messages from being printed until timestamp `t + 10`).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the `Logger` class:

*   `Logger()` Initializes the `logger` object.
*   `bool shouldPrintMessage(int timestamp, string message)` Returns `true` if the `message` should be printed in the given `timestamp`, otherwise returns `false`.

**Example 1:**

**Input**
\[ "Logger ",  "shouldPrintMessage ",  "shouldPrintMessage ",  "shouldPrintMessage ",  "shouldPrintMessage ",  "shouldPrintMessage ",  "shouldPrintMessage "\]
\[\[\], \[1,  "foo "\], \[2,  "bar "\], \[3,  "foo "\], \[8,  "bar "\], \[10,  "foo "\], \[11,  "foo "\]\]
**Output**
\[null, true, true, false, false, false, true\]

**Explanation**
Logger logger = new Logger();
logger.shouldPrintMessage(1,  "foo ");  // return true, next allowed timestamp for  "foo " is 1 + 10 = 11
logger.shouldPrintMessage(2,  "bar ");  // return true, next allowed timestamp for  "bar " is 2 + 10 = 12
logger.shouldPrintMessage(3,  "foo ");  // 3 < 11, return false
logger.shouldPrintMessage(8,  "bar ");  // 8 < 12, return false
logger.shouldPrintMessage(10,  "foo "); // 10 < 11, return false
logger.shouldPrintMessage(11,  "foo "); // 11 >= 11, return true, next allowed timestamp for  "foo " is 11 + 10 = 21

**Constraints:**

*   `0 <= timestamp <= 109`
*   Every `timestamp` will be passed in non-decreasing order (chronological order).
*   `1 <= message.length <= 30`
*   At most `104` calls will be made to `shouldPrintMessage`.
Sort Transformed Array

Given a **sorted** integer array `nums` and three integers `a`, `b` and `c`, apply a quadratic function of the form `f(x) = ax2 + bx + c` to each element `nums[i]` in the array, and return _the array in a sorted order_.

**Example 1:**

**Input:** nums = \[-4,-2,2,4\], a = 1, b = 3, c = 5
**Output:** \[3,9,15,33\]

**Example 2:**

**Input:** nums = \[-4,-2,2,4\], a = -1, b = 3, c = 5
**Output:** \[-23,-5,1,7\]

**Constraints:**

*   `1 <= nums.length <= 200`
*   `-100 <= nums[i], a, b, c <= 100`
*   `nums` is sorted in **ascending** order.

**Follow up:** Could you solve it in `O(n)` time?
Bomb Enemy

Given an `m x n` matrix `grid` where each cell is either a wall `'W'`, an enemy `'E'` or empty `'0'`, return _the maximum enemies you can kill using one bomb_. You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.

**Example 1:**

**Input:** grid = \[\[ "0 ", "E ", "0 ", "0 "\],\[ "E ", "0 ", "W ", "E "\],\[ "0 ", "E ", "0 ", "0 "\]\]
**Output:** 3

**Example 2:**

**Input:** grid = \[\[ "W ", "W ", "W "\],\[ "0 ", "0 ", "0 "\],\[ "E ", "E ", "E "\]\]
**Output:** 1

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 500`
*   `grid[i][j]` is either `'W'`, `'E'`, or `'0'`.
Design Hit Counter

Design a hit counter which counts the number of hits received in the past `5` minutes (i.e., the past `300` seconds).

Your system should accept a `timestamp` parameter (**in seconds** granularity), and you may assume that calls are being made to the system in chronological order (i.e., `timestamp` is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the `HitCounter` class:

*   `HitCounter()` Initializes the object of the hit counter system.
*   `void hit(int timestamp)` Records a hit that happened at `timestamp` (**in seconds**). Several hits may happen at the same `timestamp`.
*   `int getHits(int timestamp)` Returns the number of hits in the past 5 minutes from `timestamp` (i.e., the past `300` seconds).

**Example 1:**

**Input**
\[ "HitCounter ",  "hit ",  "hit ",  "hit ",  "getHits ",  "hit ",  "getHits ",  "getHits "\]
\[\[\], \[1\], \[2\], \[3\], \[4\], \[300\], \[300\], \[301\]\]
**Output**
\[null, null, null, null, 3, null, 4, 3\]

**Explanation**
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

**Constraints:**

*   `1 <= timestamp <= 2 * 109`
*   All the calls are being made to the system in chronological order (i.e., `timestamp` is monotonically increasing).
*   At most `300` calls will be made to `hit` and `getHits`.

**Follow up:** What if the number of hits per second could be huge? Does your design scale?
Max Sum of Rectangle No Larger Than K

Given an `m x n` matrix `matrix` and an integer `k`, return _the max sum of a rectangle in the matrix such that its sum is no larger than_ `k`.

It is **guaranteed** that there will be a rectangle with a sum no larger than `k`.

**Example 1:**

**Input:** matrix = \[\[1,0,1\],\[0,-2,3\]\], k = 2
**Output:** 2
**Explanation:** Because the sum of the blue rectangle \[\[0, 1\], \[-2, 3\]\] is 2, and 2 is the max number no larger than k (k = 2).

**Example 2:**

**Input:** matrix = \[\[2,2,-1\]\], k = 3
**Output:** 3

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 100`
*   `-100 <= matrix[i][j] <= 100`
*   `-105 <= k <= 105`

**Follow up:** What if the number of rows is much larger than the number of columns?
Nested List Weight Sum II

You are given a nested list of integers `nestedList`. Each element is either an integer or a list whose elements may also be integers or other lists.

The **depth** of an integer is the number of lists that it is inside of. For example, the nested list `[1,[2,2],[[3],2],1]` has each integer's value set to its **depth**. Let `maxDepth` be the **maximum depth** of any integer.

The **weight** of an integer is `maxDepth - (the depth of the integer) + 1`.

Return _the sum of each integer in_ `nestedList` _multiplied by its **weight**_.

**Example 1:**

**Input:** nestedList = \[\[1,1\],2,\[1,1\]\]
**Output:** 8
**Explanation:** Four 1's with a weight of 1, one 2 with a weight of 2.
1\*1 + 1\*1 + 2\*2 + 1\*1 + 1\*1 = 8

**Example 2:**

**Input:** nestedList = \[1,\[4,\[6\]\]\]
**Output:** 17
**Explanation:** One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
1\*3 + 4\*2 + 6\*1 = 17

**Constraints:**

*   `1 <= nestedList.length <= 50`
*   The values of the integers in the nested list is in the range `[-100, 100]`.
*   The maximum **depth** of any integer is less than or equal to `50`.
Water and Jug Problem

You are given two jugs with capacities `jug1Capacity` and `jug2Capacity` liters. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly `targetCapacity` liters using these two jugs.

If `targetCapacity` liters of water are measurable, you must have `targetCapacity` liters of water contained **within one or both buckets** by the end.

Operations allowed:

*   Fill any of the jugs with water.
*   Empty any of the jugs.
*   Pour water from one jug into another till the other jug is completely full, or the first jug itself is empty.

**Example 1:**

**Input:** jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
**Output:** true
**Explanation:** The famous [Die Hard](https://www.youtube.com/watch?v=BVtQNK_ZUJg&ab_channel=notnek01) example 

**Example 2:**

**Input:** jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
**Output:** false

**Example 3:**

**Input:** jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
**Output:** true

**Constraints:**

*   `1 <= jug1Capacity, jug2Capacity, targetCapacity <= 106`
Find Leaves of Binary Tree

Given the `root` of a binary tree, collect a tree's nodes as if you were doing this:

*   Collect all the leaf nodes.
*   Remove all the leaf nodes.
*   Repeat until the tree is empty.

**Example 1:**

**Input:** root = \[1,2,3,4,5\]
**Output:** \[\[4,5,3\],\[2\],\[1\]\]
Explanation:
\[\[3,5,4\],\[2\],\[1\]\] and \[\[3,4,5\],\[2\],\[1\]\] are also considered correct answers since per each level it does not matter the order on which elements are returned.

**Example 2:**

**Input:** root = \[1\]
**Output:** \[\[1\]\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 100]`.
*   `-100 <= Node.val <= 100`
Valid Perfect Square

Given a positive integer num, return `true` _if_ `num` _is a perfect square or_ `false` _otherwise_.

A **perfect square** is an integer that is the square of an integer. In other words, it is the product of some integer with itself.

You must not use any built-in library function, such as `sqrt`.

**Example 1:**

**Input:** num = 16
**Output:** true
**Explanation:** We return true because 4 \* 4 = 16 and 4 is an integer.

**Example 2:**

**Input:** num = 14
**Output:** false
**Explanation:** We return false because 3.742 \* 3.742 = 14 and 3.742 is not an integer.

**Constraints:**

*   `1 <= num <= 231 - 1`
Largest Divisible Subset

Given a set of **distinct** positive integers `nums`, return the largest subset `answer` such that every pair `(answer[i], answer[j])` of elements in this subset satisfies:

*   `answer[i] % answer[j] == 0`, or
*   `answer[j] % answer[i] == 0`

If there are multiple solutions, return any of them.

**Example 1:**

**Input:** nums = \[1,2,3\]
**Output:** \[1,2\]
**Explanation:** \[1,3\] is also accepted.

**Example 2:**

**Input:** nums = \[1,2,4,8\]
**Output:** \[1,2,4,8\]

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 2 * 109`
*   All the integers in `nums` are **unique**.
Plus One Linked List

Given a non-negative integer represented as a linked list of digits, _plus one to the integer_.

The digits are stored such that the most significant digit is at the `head` of the list.

**Example 1:**

**Input:** head = \[1,2,3\]
**Output:** \[1,2,4\]

**Example 2:**

**Input:** head = \[0\]
**Output:** \[1\]

**Constraints:**

*   The number of nodes in the linked list is in the range `[1, 100]`.
*   `0 <= Node.val <= 9`
*   The number represented by the linked list does not contain leading zeros except for the zero itself.
Range Addition

You are given an integer `length` and an array `updates` where `updates[i] = [startIdxi, endIdxi, inci]`.

You have an array `arr` of length `length` with all zeros, and you have some operation to apply on `arr`. In the `ith` operation, you should increment all the elements `arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi]` by `inci`.

Return `arr` _after applying all the_ `updates`.

**Example 1:**

**Input:** length = 5, updates = \[\[1,3,2\],\[2,4,3\],\[0,2,-2\]\]
**Output:** \[-2,0,3,5,3\]

**Example 2:**

**Input:** length = 10, updates = \[\[2,4,6\],\[5,6,8\],\[1,9,-4\]\]
**Output:** \[0,-4,2,2,2,4,4,-4,-4,-4\]

**Constraints:**

*   `1 <= length <= 105`
*   `0 <= updates.length <= 104`
*   `0 <= startIdxi <= endIdxi < length`
*   `-1000 <= inci <= 1000`
Sum of Two Integers

Given two integers `a` and `b`, return _the sum of the two integers without using the operators_ `+` _and_ `-`.

**Example 1:**

**Input:** a = 1, b = 2
**Output:** 3

**Example 2:**

**Input:** a = 2, b = 3
**Output:** 5

**Constraints:**

*   `-1000 <= a, b <= 1000`
Super Pow

Your task is to calculate `ab` mod `1337` where `a` is a positive integer and `b` is an extremely large positive integer given in the form of an array.

**Example 1:**

**Input:** a = 2, b = \[3\]
**Output:** 8

**Example 2:**

**Input:** a = 2, b = \[1,0\]
**Output:** 1024

**Example 3:**

**Input:** a = 1, b = \[4,3,3,8,5,2\]
**Output:** 1

**Constraints:**

*   `1 <= a <= 231 - 1`
*   `1 <= b.length <= 2000`
*   `0 <= b[i] <= 9`
*   `b` does not contain leading zeros.
Find K Pairs with Smallest Sums

You are given two integer arrays `nums1` and `nums2` sorted in **ascending order** and an integer `k`.

Define a pair `(u, v)` which consists of one element from the first array and one element from the second array.

Return _the_ `k` _pairs_ `(u1, v1), (u2, v2), ..., (uk, vk)` _with the smallest sums_.

**Example 1:**

**Input:** nums1 = \[1,7,11\], nums2 = \[2,4,6\], k = 3
**Output:** \[\[1,2\],\[1,4\],\[1,6\]\]
**Explanation:** The first 3 pairs are returned from the sequence: \[1,2\],\[1,4\],\[1,6\],\[7,2\],\[7,4\],\[11,2\],\[7,6\],\[11,4\],\[11,6\]

**Example 2:**

**Input:** nums1 = \[1,1,2\], nums2 = \[1,2,3\], k = 2
**Output:** \[\[1,1\],\[1,1\]\]
**Explanation:** The first 2 pairs are returned from the sequence: \[1,1\],\[1,1\],\[1,2\],\[2,1\],\[1,2\],\[2,2\],\[1,3\],\[1,3\],\[2,3\]

**Example 3:**

**Input:** nums1 = \[1,2\], nums2 = \[3\], k = 3
**Output:** \[\[1,3\],\[2,3\]\]
**Explanation:** All possible pairs are returned from the sequence: \[1,3\],\[2,3\]

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 105`
*   `-109 <= nums1[i], nums2[i] <= 109`
*   `nums1` and `nums2` both are sorted in **ascending order**.
*   `1 <= k <= 104`
Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from `1` to `n`. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API `int guess(int num)`, which returns three possible results:

*   `-1`: Your guess is higher than the number I picked (i.e. `num > pick`).
*   `1`: Your guess is lower than the number I picked (i.e. `num < pick`).
*   `0`: your guess is equal to the number I picked (i.e. `num == pick`).

Return _the number that I picked_.

**Example 1:**

**Input:** n = 10, pick = 6
**Output:** 6

**Example 2:**

**Input:** n = 1, pick = 1
**Output:** 1

**Example 3:**

**Input:** n = 2, pick = 1
**Output:** 1

**Constraints:**

*   `1 <= n <= 231 - 1`
*   `1 <= pick <= n`
Guess Number Higher or Lower II

We are playing the Guessing Game. The game will work as follows:

1.  I pick a number between `1` and `n`.
2.  You guess a number.
3.  If you guess the right number, **you win the game**.
4.  If you guess the wrong number, then I will tell you whether the number I picked is **higher or lower**, and you will continue guessing.
5.  Every time you guess a wrong number `x`, you will pay `x` dollars. If you run out of money, **you lose the game**.

Given a particular `n`, return _the minimum amount of money you need to **guarantee a win regardless of what number I pick**_.

**Example 1:**

**Input:** n = 10
**Output:** 16
**Explanation:** The winning strategy is as follows:
- The range is \[1,10\]. Guess 7.
    - If this is my number, your total is $0. Otherwise, you pay $7.
    - If my number is higher, the range is \[8,10\]. Guess 9.
        - If this is my number, your total is $7. Otherwise, you pay $9.
        - If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
        - If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
    - If my number is lower, the range is \[1,6\]. Guess 3.
        - If this is my number, your total is $7. Otherwise, you pay $3.
        - If my number is higher, the range is \[4,6\]. Guess 5.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
            - If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
            - If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
        - If my number is lower, the range is \[1,2\]. Guess 1.
            - If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
            - If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.

**Example 2:**

**Input:** n = 1
**Output:** 0
**Explanation:** There is only one possible number, so you can guess 1 and not have to pay anything.

**Example 3:**

**Input:** n = 2
**Output:** 1
**Explanation:** There are two possible numbers, 1 and 2.
- Guess 1.
    - If this is my number, your total is $0. Otherwise, you pay $1.
    - If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.

**Constraints:**

*   `1 <= n <= 200`