bowang0911/leetcode huggingface dataset:
Poor Pigs

There are `buckets` buckets of liquid, where **exactly one** of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have `minutesToTest` minutes to determine which bucket is poisonous.

You can feed the pigs according to these steps:

1.  Choose some live pigs to feed.
2.  For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time. Each pig can feed from any number of buckets, and each bucket can be fed from by any number of pigs.
3.  Wait for `minutesToDie` minutes. You may **not** feed any other pigs during this time.
4.  After `minutesToDie` minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
5.  Repeat this process until you run out of time.

Given `buckets`, `minutesToDie`, and `minutesToTest`, return _the **minimum** number of pigs needed to figure out which bucket is poisonous within the allotted time_.

**Example 1:**

**Input:** buckets = 4, minutesToDie = 15, minutesToTest = 15
**Output:** 2
**Explanation:** We can determine the poisonous bucket as follows:
At time 0, feed the first pig buckets 1 and 2, and feed the second pig buckets 2 and 3.
At time 15, there are 4 possible outcomes:
- If only the first pig dies, then bucket 1 must be poisonous.
- If only the second pig dies, then bucket 3 must be poisonous.
- If both pigs die, then bucket 2 must be poisonous.
- If neither pig dies, then bucket 4 must be poisonous.

**Example 2:**

**Input:** buckets = 4, minutesToDie = 15, minutesToTest = 30
**Output:** 2
**Explanation:** We can determine the poisonous bucket as follows:
At time 0, feed the first pig bucket 1, and feed the second pig bucket 2.
At time 15, there are 2 possible outcomes:
- If either pig dies, then the poisonous bucket is the one it was fed.
- If neither pig dies, then feed the first pig bucket 3, and feed the second pig bucket 4.
At time 30, one of the two pigs must die, and the poisonous bucket is the one it was fed.

**Constraints:**

*   `1 <= buckets <= 1000`
*   `1 <= minutesToDie <= minutesToTest <= 100`
Repeated Substring Pattern

Given a string `s`, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

**Example 1:**

**Input:** s =  "abab "
**Output:** true
**Explanation:** It is the substring  "ab " twice.

**Example 2:**

**Input:** s =  "aba "
**Output:** false

**Example 3:**

**Input:** s =  "abcabcabcabc "
**Output:** true
**Explanation:** It is the substring  "abc " four times or the substring  "abcabc " twice.

**Constraints:**

*   `1 <= s.length <= 104`
*   `s` consists of lowercase English letters.
LFU Cache

Design and implement a data structure for a [Least Frequently Used (LFU)](https://en.wikipedia.org/wiki/Least_frequently_used) cache.

Implement the `LFUCache` class:

*   `LFUCache(int capacity)` Initializes the object with the `capacity` of the data structure.
*   `int get(int key)` Gets the value of the `key` if the `key` exists in the cache. Otherwise, returns `-1`.
*   `void put(int key, int value)` Update the value of the `key` if present, or inserts the `key` if not already present. When the cache reaches its `capacity`, it should invalidate and remove the **least frequently used** key before inserting a new item. For this problem, when there is a **tie** (i.e., two or more keys with the same frequency), the **least recently used** `key` would be invalidated.

To determine the least frequently used key, a **use counter** is maintained for each key in the cache. The key with the smallest **use counter** is the least frequently used key.

When a key is first inserted into the cache, its **use counter** is set to `1` (due to the `put` operation). The **use counter** for a key in the cache is incremented either a `get` or `put` operation is called on it.

The functions `get` and `put` must each run in `O(1)` average time complexity.

**Example 1:**

**Input**
\[ "LFUCache ",  "put ",  "put ",  "get ",  "put ",  "get ",  "get ",  "put ",  "get ",  "get ",  "get "\]
\[\[2\], \[1, 1\], \[2, 2\], \[1\], \[3, 3\], \[2\], \[3\], \[4, 4\], \[1\], \[3\], \[4\]\]
**Output**
\[null, null, null, 1, null, -1, 3, null, -1, 3, 4\]

**Explanation**
// cnt(x) = the use counter for key x
// cache=\[\] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=\[1,\_\], cnt(1)=1
lfu.put(2, 2);   // cache=\[2,1\], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=\[1,2\], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=\[3,1\], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=\[3,1\], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=\[4,3\], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=\[3,4\], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=\[4,3\], cnt(4)=2, cnt(3)=3

**Constraints:**

*   `1 <= capacity <= 104`
*   `0 <= key <= 105`
*   `0 <= value <= 109`
*   At most `2 * 105` calls will be made to `get` and `put`.
Hamming Distance

The [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) between two integers is the number of positions at which the corresponding bits are different.

Given two integers `x` and `y`, return _the **Hamming distance** between them_.

**Example 1:**

**Input:** x = 1, y = 4
**Output:** 2
**Explanation:**
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

**Example 2:**

**Input:** x = 3, y = 1
**Output:** 1

**Constraints:**

*   `0 <= x, y <= 231 - 1`
Minimum Moves to Equal Array Elements II

Given an integer array `nums` of size `n`, return _the minimum number of moves required to make all array elements equal_.

In one move, you can increment or decrement an element of the array by `1`.

Test cases are designed so that the answer will fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = \[1,2,3\]
**Output:** 2
**Explanation:**
Only two moves are needed (remember each move increments or decrements one element):
\[1,2,3\]  =>  \[2,2,3\]  =>  \[2,2,2\]

**Example 2:**

**Input:** nums = \[1,10,2,9\]
**Output:** 16

**Constraints:**

*   `n == nums.length`
*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
Island Perimeter

You are given `row x col` `grid` representing a map where `grid[i][j] = 1` represents land and `grid[i][j] = 0` represents water.

Grid cells are connected **horizontally/vertically** (not diagonally). The `grid` is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes ", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

**Example 1:**

**Input:** grid = \[\[0,1,0,0\],\[1,1,1,0\],\[0,1,0,0\],\[1,1,0,0\]\]
**Output:** 16
**Explanation:** The perimeter is the 16 yellow stripes in the image above.

**Example 2:**

**Input:** grid = \[\[1\]\]
**Output:** 4

**Example 3:**

**Input:** grid = \[\[1,0\]\]
**Output:** 4

**Constraints:**

*   `row == grid.length`
*   `col == grid[i].length`
*   `1 <= row, col <= 100`
*   `grid[i][j]` is `0` or `1`.
*   There is exactly one island in `grid`.
Can I Win

In the "100 game " two players take turns adding, to a running total, any integer from `1` to `10`. The player who first causes the running total to **reach or exceed** 100 wins.

What if we change the game so that players **cannot** re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers `maxChoosableInteger` and `desiredTotal`, return `true` if the first player to move can force a win, otherwise, return `false`. Assume both players play **optimally**.

**Example 1:**

**Input:** maxChoosableInteger = 10, desiredTotal = 11
**Output:** false
**Explanation:**
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

**Example 2:**

**Input:** maxChoosableInteger = 10, desiredTotal = 0
**Output:** true

**Example 3:**

**Input:** maxChoosableInteger = 10, desiredTotal = 1
**Output:** true

**Constraints:**

*   `1 <= maxChoosableInteger <= 20`
*   `0 <= desiredTotal <= 300`
Optimal Account Balancing

You are given an array of transactions `transactions` where `transactions[i] = [fromi, toi, amounti]` indicates that the person with `ID = fromi` gave `amounti $` to the person with `ID = toi`.

Return _the minimum number of transactions required to settle the debt_.

**Example 1:**

**Input:** transactions = \[\[0,1,10\],\[2,0,5\]\]
**Output:** 2
**Explanation:**
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

**Example 2:**

**Input:** transactions = \[\[0,1,10\],\[1,0,1\],\[1,2,5\],\[2,0,5\]\]
**Output:** 1
**Explanation:**
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

**Constraints:**

*   `1 <= transactions.length <= 8`
*   `transactions[i].length == 3`
*   `0 <= fromi, toi < 12`
*   `fromi != toi`
*   `1 <= amounti <= 100`
Count The Repetitions

We define `str = [s, n]` as the string `str` which consists of the string `s` concatenated `n` times.

*   For example, `str == [ "abc ", 3] == "abcabcabc "`.

We define that string `s1` can be obtained from string `s2` if we can remove some characters from `s2` such that it becomes `s1`.

*   For example, `s1 = "abc "` can be obtained from `s2 = "ab**dbe**c "` based on our definition by removing the bolded underlined characters.

You are given two strings `s1` and `s2` and two integers `n1` and `n2`. You have the two strings `str1 = [s1, n1]` and `str2 = [s2, n2]`.

Return _the maximum integer_ `m` _such that_ `str = [str2, m]` _can be obtained from_ `str1`.

**Example 1:**

**Input:** s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
**Output:** 2

**Example 2:**

**Input:** s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
**Output:** 1

**Constraints:**

*   `1 <= s1.length, s2.length <= 100`
*   `s1` and `s2` consist of lowercase English letters.
*   `1 <= n1, n2 <= 106`
Unique Substrings in Wraparound String

We define the string `base` to be the infinite wraparound string of `"abcdefghijklmnopqrstuvwxyz "`, so `base` will look like this:

*   `"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.... "`.

Given a string `s`, return _the number of **unique non-empty substrings** of_ `s` _are present in_ `base`.

**Example 1:**

**Input:** s =  "a "
**Output:** 1
**Explanation:** Only the substring  "a " of s is in base.

**Example 2:**

**Input:** s =  "cac "
**Output:** 2
**Explanation:** There are two substrings ( "a ",  "c ") of s in base.

**Example 3:**

**Input:** s =  "zab "
**Output:** 6
**Explanation:** There are six substrings ( "z ",  "a ",  "b ",  "za ",  "ab ", and  "zab ") of s in base.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of lowercase English letters.
Validate IP Address

Given a string `queryIP`, return `"IPv4 "` if IP is a valid IPv4 address, `"IPv6 "` if IP is a valid IPv6 address or `"Neither "` if IP is not a correct IP of any type.

**A valid IPv4** address is an IP in the form `"x1.x2.x3.x4 "` where `0 <= xi <= 255` and `xi` **cannot contain** leading zeros. For example, `"192.168.1.1 "` and `"192.168.1.0 "` are valid IPv4 addresses while `"192.168.01.1 "`, `"192.168.1.00 "`, and `"192.168@1.1 "` are invalid IPv4 addresses.

**A valid IPv6** address is an IP in the form `"x1:x2:x3:x4:x5:x6:x7:x8 "` where:

*   `1 <= xi.length <= 4`
*   `xi` is a **hexadecimal string** which may contain digits, lowercase English letter (`'a'` to `'f'`) and upper-case English letters (`'A'` to `'F'`).
*   Leading zeros are allowed in `xi`.

For example, "`2001:0db8:85a3:0000:0000:8a2e:0370:7334 "` and "`2001:db8:85a3:0:0:8A2E:0370:7334 "` are valid IPv6 addresses, while "`2001:0db8:85a3::8A2E:037j:7334 "` and "`02001:0db8:85a3:0000:0000:8a2e:0370:7334 "` are invalid IPv6 addresses.

**Example 1:**

**Input:** queryIP =  "172.16.254.1 "
**Output:**  "IPv4 "
**Explanation:** This is a valid IPv4 address, return  "IPv4 ".

**Example 2:**

**Input:** queryIP =  "2001:0db8:85a3:0:0:8A2E:0370:7334 "
**Output:**  "IPv6 "
**Explanation:** This is a valid IPv6 address, return  "IPv6 ".

**Example 3:**

**Input:** queryIP =  "256.256.256.256 "
**Output:**  "Neither "
**Explanation:** This is neither a IPv4 address nor a IPv6 address.

**Constraints:**

*   `queryIP` consists only of English letters, digits and the characters `'.'` and `':'`.
Convex Polygon

You are given an array of points on the **X-Y** plane `points` where `points[i] = [xi, yi]`. The points form a polygon when joined sequentially.

Return `true` if this polygon is [convex](http://en.wikipedia.org/wiki/Convex_polygon) and `false` otherwise.

You may assume the polygon formed by given points is always a [simple polygon](http://en.wikipedia.org/wiki/Simple_polygon). In other words, we ensure that exactly two edges intersect at each vertex and that edges otherwise don't intersect each other.

**Example 1:**

**Input:** points = \[\[0,0\],\[0,5\],\[5,5\],\[5,0\]\]
**Output:** true

**Example 2:**

**Input:** points = \[\[0,0\],\[0,10\],\[10,10\],\[10,0\],\[5,5\]\]
**Output:** false

**Constraints:**

*   `3 <= points.length <= 104`
*   `points[i].length == 2`
*   `-104 <= xi, yi <= 104`
*   All the given points are **unique**.
Implement Rand10() Using Rand7()

Given the **API** `rand7()` that generates a uniform random integer in the range `[1, 7]`, write a function `rand10()` that generates a uniform random integer in the range `[1, 10]`. You can only call the API `rand7()`, and you shouldn't call any other API. Please **do not** use a language's built-in random API.

Each test case will have one **internal** argument `n`, the number of times that your implemented function `rand10()` will be called while testing. Note that this is **not an argument** passed to `rand10()`.

**Example 1:**

**Input:** n = 1
**Output:** \[2\]

**Example 2:**

**Input:** n = 2
**Output:** \[2,8\]

**Example 3:**

**Input:** n = 3
**Output:** \[3,8,10\]

**Constraints:**

*   `1 <= n <= 105`

**Follow up:**

*   What is the [expected value](https://en.wikipedia.org/wiki/Expected_value) for the number of calls to `rand7()` function?
*   Could you minimize the number of calls to `rand7()`?
Encode String with Shortest Length

Given a string `s`, encode the string such that its encoded length is the shortest.

The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is being repeated exactly `k` times. `k` should be a positive integer.

If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return **any of them**.

**Example 1:**

**Input:** s =  "aaa "
**Output:**  "aaa "
**Explanation:** There is no way to encode it such that it is shorter than the input string, so we do not encode it.

**Example 2:**

**Input:** s =  "aaaaa "
**Output:**  "5\[a\] "
**Explanation:**  "5\[a\] " is shorter than  "aaaaa " by 1 character.

**Example 3:**

**Input:** s =  "aaaaaaaaaa "
**Output:**  "10\[a\] "
**Explanation:**  "a9\[a\] " or  "9\[a\]a " are also valid solutions, both of them have the same length = 5, which is the same as  "10\[a\] ".

**Constraints:**

*   `1 <= s.length <= 150`
*   `s` consists of only lowercase English letters.
Concatenated Words

Given an array of strings `words` (**without duplicates**), return _all the **concatenated words** in the given list of_ `words`.

A **concatenated word** is defined as a string that is comprised entirely of at least two shorter words (not necesssarily distinct) in the given array.

**Example 1:**

**Input:** words = \[ "cat ", "cats ", "catsdogcats ", "dog ", "dogcatsdog ", "hippopotamuses ", "rat ", "ratcatdogcat "\]
**Output:** \[ "catsdogcats ", "dogcatsdog ", "ratcatdogcat "\]
**Explanation:**  "catsdogcats " can be concatenated by  "cats ",  "dog " and  "cats "; 
 "dogcatsdog " can be concatenated by  "dog ",  "cats " and  "dog "; 
 "ratcatdogcat " can be concatenated by  "rat ",  "cat ",  "dog " and  "cat ".

**Example 2:**

**Input:** words = \[ "cat ", "dog ", "catdog "\]
**Output:** \[ "catdog "\]

**Constraints:**

*   `1 <= words.length <= 104`
*   `1 <= words[i].length <= 30`
*   `words[i]` consists of only lowercase English letters.
*   All the strings of `words` are **unique**.
*   `1 <= sum(words[i].length) <= 105`
Matchsticks to Square

You are given an integer array `matchsticks` where `matchsticks[i]` is the length of the `ith` matchstick. You want to use **all the matchsticks** to make one square. You **should not break** any stick, but you can link them up, and each matchstick must be used **exactly one time**.

Return `true` if you can make this square and `false` otherwise.

**Example 1:**

**Input:** matchsticks = \[1,1,2,2,2\]
**Output:** true
**Explanation:** You can form a square with length 2, one side of the square came two sticks with length 1.

**Example 2:**

**Input:** matchsticks = \[3,3,3,3,4\]
**Output:** false
**Explanation:** You cannot find a way to form a square with all the matchsticks.

**Constraints:**

*   `1 <= matchsticks.length <= 15`
*   `1 <= matchsticks[i] <= 108`
Ones and Zeroes

You are given an array of binary strings `strs` and two integers `m` and `n`.

Return _the size of the largest subset of `strs` such that there are **at most**_ `m` `0`_'s and_ `n` `1`_'s in the subset_.

A set `x` is a **subset** of a set `y` if all elements of `x` are also elements of `y`.

**Example 1:**

**Input:** strs = \[ "10 ", "0001 ", "111001 ", "1 ", "0 "\], m = 5, n = 3
**Output:** 4
**Explanation:** The largest subset with at most 5 0's and 3 1's is { "10 ",  "0001 ",  "1 ",  "0 "}, so the answer is 4.
Other valid but smaller subsets include { "0001 ",  "1 "} and { "10 ",  "1 ",  "0 "}.
{ "111001 "} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

**Example 2:**

**Input:** strs = \[ "10 ", "0 ", "1 "\], m = 1, n = 1
**Output:** 2
**Explanation:** The largest subset is { "0 ",  "1 "}, so the answer is 2.

**Constraints:**

*   `1 <= strs.length <= 600`
*   `1 <= strs[i].length <= 100`
*   `strs[i]` consists only of digits `'0'` and `'1'`.
*   `1 <= m, n <= 100`
Heaters

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of `houses` and `heaters` on a horizontal line, return _the minimum radius standard of heaters so that those heaters could cover all houses._

**Notice** that all the `heaters` follow your radius standard, and the warm radius will the same.

**Example 1:**

**Input:** houses = \[1,2,3\], heaters = \[2\]
**Output:** 1
**Explanation:** The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

**Example 2:**

**Input:** houses = \[1,2,3,4\], heaters = \[1,4\]
**Output:** 1
**Explanation:** The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

**Example 3:**

**Input:** houses = \[1,5\], heaters = \[2\]
**Output:** 3

**Constraints:**

*   `1 <= houses.length, heaters.length <= 3 * 104`
*   `1 <= houses[i], heaters[i] <= 109`
Number Complement

The **complement** of an integer is the integer you get when you flip all the `0`'s to `1`'s and all the `1`'s to `0`'s in its binary representation.

*   For example, The integer `5` is `"101 "` in binary and its **complement** is `"010 "` which is the integer `2`.

Given an integer `num`, return _its complement_.

**Example 1:**

**Input:** num = 5
**Output:** 2
**Explanation:** The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

**Example 2:**

**Input:** num = 1
**Output:** 0
**Explanation:** The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

**Constraints:**

*   `1 <= num < 231`

**Note:** This question is the same as 1009: [https://leetcode.com/problems/complement-of-base-10-integer/](https://leetcode.com/problems/complement-of-base-10-integer/)
Total Hamming Distance

The [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) between two integers is the number of positions at which the corresponding bits are different.

Given an integer array `nums`, return _the sum of **Hamming distances** between all the pairs of the integers in_ `nums`.

**Example 1:**

**Input:** nums = \[4,14,2\]
**Output:** 6
**Explanation:** In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

**Example 2:**

**Input:** nums = \[4,14,4\]
**Output:** 4

**Constraints:**

*   `1 <= nums.length <= 104`
*   `0 <= nums[i] <= 109`
*   The answer for the given input will fit in a **32-bit** integer.
Generate Random Point in a Circle

Given the radius and the position of the center of a circle, implement the function `randPoint` which generates a uniform random point inside the circle.

Implement the `Solution` class:

*   `Solution(double radius, double x_center, double y_center)` initializes the object with the radius of the circle `radius` and the position of the center `(x_center, y_center)`.
*   `randPoint()` returns a random point inside the circle. A point on the circumference of the circle is considered to be in the circle. The answer is returned as an array `[x, y]`.

**Example 1:**

**Input**
\[ "Solution ",  "randPoint ",  "randPoint ",  "randPoint "\]
\[\[1.0, 0.0, 0.0\], \[\], \[\], \[\]\]
**Output**
\[null, \[-0.02493, -0.38077\], \[0.82314, 0.38945\], \[0.36572, 0.17248\]\]

**Explanation**
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return \[-0.02493, -0.38077\]
solution.randPoint(); // return \[0.82314, 0.38945\]
solution.randPoint(); // return \[0.36572, 0.17248\]

**Constraints:**

*   `0 < radius <= 108`
*   `-107 <= x_center, y_center <= 107`
*   At most `3 * 104` calls will be made to `randPoint`.
Largest Palindrome Product

Given an integer n, return _the **largest palindromic integer** that can be represented as the product of two `n`\-digits integers_. Since the answer can be very large, return it **modulo** `1337`.

**Example 1:**

**Input:** n = 2
**Output:** 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

**Example 2:**

**Input:** n = 1
**Output:** 9

**Constraints:**

*   `1 <= n <= 8`