bowang0911/leetcode huggingface dataset:
Find the Array Concatenation Value

You are given a **0-indexed** integer array `nums`.

The **concatenation** of two numbers is the number formed by concatenating their numerals.

*   For example, the concatenation of `15`, `49` is `1549`.

The **concatenation value** of `nums` is initially equal to `0`. Perform this operation until `nums` becomes empty:

*   If there exists more than one number in `nums`, pick the first element and last element in `nums` respectively and add the value of their concatenation to the **concatenation value** of `nums`, then delete the first and last element from `nums`.
*   If one element exists, add its value to the **concatenation value** of `nums`, then delete it.

Return _the concatenation value of the `nums`_.

**Example 1:**

**Input:** nums = \[7,52,2,4\]
**Output:** 596
**Explanation:** Before performing any operation, nums is \[7,52,2,4\] and concatenation value is 0.
 - In the first operation:
We pick the first element, 7, and the last element, 4.
Their concatenation is 74, and we add it to the concatenation value, so it becomes equal to 74.
Then we delete them from nums, so nums becomes equal to \[52,2\].
 - In the second operation:
We pick the first element, 52, and the last element, 2.
Their concatenation is 522, and we add it to the concatenation value, so it becomes equal to 596.
Then we delete them from the nums, so nums becomes empty.
Since the concatenation value is 596 so the answer is 596.

**Example 2:**

**Input:** nums = \[5,14,13,8,12\]
**Output:** 673
**Explanation:** Before performing any operation, nums is \[5,14,13,8,12\] and concatenation value is 0.
 - In the first operation:
We pick the first element, 5, and the last element, 12.
Their concatenation is 512, and we add it to the concatenation value, so it becomes equal to 512.
Then we delete them from the nums, so nums becomes equal to \[14,13,8\].
 - In the second operation:
We pick the first element, 14, and the last element, 8.
Their concatenation is 148, and we add it to the concatenation value, so it becomes equal to 660.
Then we delete them from the nums, so nums becomes equal to \[13\].
 - In the third operation:
nums has only one element, so we pick 13 and add it to the concatenation value, so it becomes equal to 673.
Then we delete it from nums, so nums become empty.
Since the concatenation value is 673 so the answer is 673.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 104`

.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0;  } .spoiler {overflow:hidden;} .spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;} .spoilerbutton\[value="Show Message"\] + .spoiler > div {margin-top:-500%;} .spoilerbutton\[value="Hide Message"\] + .spoiler {padding:5px;}
Count the Number of Fair Pairs

Given a **0-indexed** integer array `nums` of size `n` and two integers `lower` and `upper`, return _the number of fair pairs_.

A pair `(i, j)` is **fair** if:

*   `0 <= i < j < n`, and
*   `lower <= nums[i] + nums[j] <= upper`

**Example 1:**

**Input:** nums = \[0,1,7,4,4,5\], lower = 3, upper = 6
**Output:** 6
**Explanation:** There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

**Example 2:**

**Input:** nums = \[1,7,9,2,5\], lower = 11, upper = 11
**Output:** 1
**Explanation:** There is a single fair pair: (2,3).

**Constraints:**

*   `1 <= nums.length <= 105`
*   `nums.length == n`
*   `-109 <= nums[i] <= 109`
*   `-109 <= lower <= upper <= 109`
Substring XOR Queries

You are given a **binary string** `s`, and a **2D** integer array `queries` where `queries[i] = [firsti, secondi]`.

For the `ith` query, find the **shortest substring** of `s` whose **decimal value**, `val`, yields `secondi` when **bitwise XORed** with `firsti`. In other words, `val ^ firsti == secondi`.

The answer to the `ith` query is the endpoints (**0-indexed**) of the substring `[lefti, righti]` or `[-1, -1]` if no such substring exists. If there are multiple answers, choose the one with the **minimum** `lefti`.

_Return an array_ `ans` _where_ `ans[i] = [lefti, righti]` _is the answer to the_ `ith` _query._

A **substring** is a contiguous non-empty sequence of characters within a string.

**Example 1:**

**Input:** s =  "101101 ", queries = \[\[0,5\],\[1,2\]\]
**Output:** \[\[0,2\],\[2,3\]\]
**Explanation:** For the first query the substring in range `[0,2]` is ** "101 "** which has a decimal value of **`5`**, and **`5 ^ 0 = 5`**, hence the answer to the first query is `[0,2]`. In the second query, the substring in range `[2,3]` is ** "11 ",** and has a decimal value of **3**, and **3 `^ 1 = 2`**. So, `[2,3]` is returned for the second query. 

**Example 2:**

**Input:** s =  "0101 ", queries = \[\[12,8\]\]
**Output:** \[\[-1,-1\]\]
**Explanation:** In this example there is no substring that answers the query, hence `[-1,-1] is returned`.

**Example 3:**

**Input:** s =  "1 ", queries = \[\[4,5\]\]
**Output:** \[\[0,0\]\]
**Explanation:** For this example, the substring in range `[0,0]` has a decimal value of **`1`**, and **`1 ^ 4 = 5`**. So, the answer is `[0,0]`.

**Constraints:**

*   `1 <= s.length <= 104`
*   `s[i]` is either `'0'` or `'1'`.
*   `1 <= queries.length <= 105`
*   `0 <= firsti, secondi <= 109`
Subsequence With the Minimum Score

You are given two strings `s` and `t`.

You are allowed to remove any number of characters from the string `t`.

The score of the string is `0` if no characters are removed from the string `t`, otherwise:

*   Let `left` be the minimum index among all removed characters.
*   Let `right` be the maximum index among all removed characters.

Then the score of the string is `right - left + 1`.

Return _the minimum possible score to make_ `t` _a subsequence of_ `s`_._

A **subsequence** of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., `"ace "` is a subsequence of `"abcde "` while `"aec "` is not).

**Example 1:**

**Input:** s =  "abacaba ", t =  "bzaa "
**Output:** 1
**Explanation:** In this example, we remove the character  "z " at index 1 (0-indexed).
The string t becomes  "baa " which is a subsequence of the string  "abacaba " and the score is 1 - 1 + 1 = 1.
It can be proven that 1 is the minimum score that we can achieve.

**Example 2:**

**Input:** s =  "cde ", t =  "xyz "
**Output:** 3
**Explanation:** In this example, we remove characters  "x ",  "y " and  "z " at indices 0, 1, and 2 (0-indexed).
The string t becomes  " " which is a subsequence of the string  "cde " and the score is 2 - 0 + 1 = 3.
It can be proven that 3 is the minimum score that we can achieve.

**Constraints:**

*   `1 <= s.length, t.length <= 105`
*   `s` and `t` consist of only lowercase English letters.
Maximum Difference by Remapping a Digit

You are given an integer `num`. You know that Danny Mittal will sneakily **remap** one of the `10` possible digits (`0` to `9`) to another digit.

Return _the difference between the maximum and minimum_ _values Danny can make by remapping **exactly** **one** digit_ _in_ `num`.

**Notes:**

*   When Danny remaps a digit d1 to another digit d2, Danny replaces all occurrences of `d1` in `num` with `d2`.
*   Danny can remap a digit to itself, in which case `num` does not change.
*   Danny can remap different digits for obtaining minimum and maximum values respectively.
*   The resulting number after remapping can contain leading zeroes.
*   We mentioned "Danny Mittal " to congratulate him on being in the top 10 in Weekly Contest 326.

**Example 1:**

**Input:** num = 11891
**Output:** 99009
**Explanation:** 
To achieve the maximum value, Danny can remap the digit 1 to the digit 9 to yield 99899.
To achieve the minimum value, Danny can remap the digit 1 to the digit 0, yielding 890.
The difference between these two numbers is 99009.

**Example 2:**

**Input:** num = 90
**Output:** 99
**Explanation:**
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
Thus, we return 99.

**Constraints:**

*   `1 <= num <= 108`
Minimum Score by Changing Two Elements

You are given a **0-indexed** integer array `nums`.

*   The **low** score of `nums` is the minimum value of `|nums[i] - nums[j]|` over all `0 <= i < j < nums.length`.
*   The **high** score of `nums` is the maximum value of `|nums[i] - nums[j]|` over all `0 <= i < j < nums.length`.
*   The **score** of `nums` is the sum of the **high** and **low** scores of nums.

To minimize the score of `nums`, we can change the value of **at most two** elements of `nums`.

Return _the **minimum** possible **score** after changing the value of **at most two** elements o_f `nums`.

Note that `|x|` denotes the absolute value of `x`.

**Example 1:**

**Input:** nums = \[1,4,3\]
**Output:** 0
**Explanation:** Change value of nums\[1\] and nums\[2\] to 1 so that nums becomes \[1,1,1\]. Now, the value of `|nums[i] - nums[j]|` is always equal to 0, so we return 0 + 0 = 0.

**Example 2:**

**Input:** nums = \[1,4,7,8,5\]
**Output:** 3
**Explanation:** Change nums\[0\] and nums\[1\] to be 6. Now nums becomes \[6,6,7,8,5\].
Our low score is achieved when i = 0 and j = 1, in which case |`nums[i] - nums[j]`| = |6 - 6| = 0.
Our high score is achieved when i = 3 and j = 4, in which case |`nums[i] - nums[j]`| = |8 - 5| = 3.
The sum of our high and low score is 3, which we can prove to be minimal.

**Constraints:**

*   `3 <= nums.length <= 105`
*   `1 <= nums[i] <= 109`
Minimum Impossible OR

You are given a **0-indexed** integer array `nums`.

We say that an integer x is **expressible** from `nums` if there exist some integers `0 <= index1 < index2 < ... < indexk < nums.length` for which `nums[index1] | nums[index2] | ... | nums[indexk] = x`. In other words, an integer is expressible if it can be written as the bitwise OR of some subsequence of `nums`.

Return _the minimum **positive non-zero integer** that is not_ _expressible from_ `nums`.

**Example 1:**

**Input:** nums = \[2,1\]
**Output:** 4
**Explanation:** 1 and 2 are already present in the array. We know that 3 is expressible, since nums\[0\] | nums\[1\] = 2 | 1 = 3. Since 4 is not expressible, we return 4.

**Example 2:**

**Input:** nums = \[5,3,2\]
**Output:** 1
**Explanation:** We can show that 1 is the smallest number that is not expressible.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 109`
Handling Sum Queries After Update

You are given two **0-indexed** arrays `nums1` and `nums2` and a 2D array `queries` of queries. There are three types of queries:

1.  For a query of type 1, `queries[i] = [1, l, r]`. Flip the values from `0` to `1` and from `1` to `0` in `nums1` from index `l` to index `r`. Both `l` and `r` are **0-indexed**.
2.  For a query of type 2, `queries[i] = [2, p, 0]`. For every index `0 <= i < n`, set `nums2[i] = nums2[i] + nums1[i] * p`.
3.  For a query of type 3, `queries[i] = [3, 0, 0]`. Find the sum of the elements in `nums2`.

Return _an array containing all the answers to the third type queries._

**Example 1:**

**Input:** nums1 = \[1,0,1\], nums2 = \[0,0,0\], queries = \[\[1,1,1\],\[2,1,0\],\[3,0,0\]\]
**Output:** \[3\]
**Explanation:** After the first query nums1 becomes \[1,1,1\]. After the second query, nums2 becomes \[1,1,1\], so the answer to the third query is 3. Thus, \[3\] is returned.

**Example 2:**

**Input:** nums1 = \[1\], nums2 = \[5\], queries = \[\[2,0,0\],\[3,0,0\]\]
**Output:** \[5\]
**Explanation:** After the first query, nums2 remains \[5\], so the answer to the second query is 5. Thus, \[5\] is returned.

**Constraints:**

*   `1 <= nums1.length,nums2.length <= 105`
*   `nums1.length = nums2.length`
*   `1 <= queries.length <= 105`
*   `queries[i].length = 3`
*   `0 <= l <= r <= nums1.length - 1`
*   `0 <= p <= 106`
*   `0 <= nums1[i] <= 1`
*   `0 <= nums2[i] <= 109`
Merge Two 2D Arrays by Summing Values

You are given two **2D** integer arrays `nums1` and `nums2.`

*   `nums1[i] = [idi, vali]` indicate that the number with the id `idi` has a value equal to `vali`.
*   `nums2[i] = [idi, vali]` indicate that the number with the id `idi` has a value equal to `vali`.

Each array contains **unique** ids and is sorted in **ascending** order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

*   Only ids that appear in at least one of the two arrays should be included in the resulting array.
*   Each id should be included **only once** and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be `0`.

Return _the resulting array_. The returned array must be sorted in ascending order by id.

**Example 1:**

**Input:** nums1 = \[\[1,2\],\[2,3\],\[4,5\]\], nums2 = \[\[1,4\],\[3,2\],\[4,1\]\]
**Output:** \[\[1,6\],\[2,3\],\[3,2\],\[4,6\]\]
**Explanation:** The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

**Example 2:**

**Input:** nums1 = \[\[2,4\],\[3,6\],\[5,5\]\], nums2 = \[\[1,3\],\[4,3\]\]
**Output:** \[\[1,3\],\[2,4\],\[3,6\],\[4,3\],\[5,5\]\]
**Explanation:** There are no common ids, so we just include each id with its value in the resulting list.

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 200`
*   `nums1[i].length == nums2[j].length == 2`
*   `1 <= idi, vali <= 1000`
*   Both arrays contain unique ids.
*   Both arrays are in strictly ascending order by id.
Minimum Operations to Reduce an Integer to 0

You are given a positive integer `n`, you can do the following operation **any** number of times:

*   Add or subtract a **power** of `2` from `n`.

Return _the **minimum** number of operations to make_ `n` _equal to_ `0`.

A number `x` is power of `2` if `x == 2i` where `i >= 0`_._

**Example 1:**

**Input:** n = 39
**Output:** 3
**Explanation:** We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

**Example 2:**

**Input:** n = 54
**Output:** 3
**Explanation:** We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

**Constraints:**

*   `1 <= n <= 105`
Count the Number of Square-Free Subsets

You are given a positive integer **0-indexed** array `nums`.

A subset of the array `nums` is **square-free** if the product of its elements is a **square-free integer**.

A **square-free integer** is an integer that is divisible by no square number other than `1`.

Return _the number of square-free non-empty subsets of the array_ **nums**. Since the answer may be too large, return it **modulo** `109 + 7`.

A **non-empty** **subset** of `nums` is an array that can be obtained by deleting some (possibly none but not all) elements from `nums`. Two subsets are different if and only if the chosen indices to delete are different.

**Example 1:**

**Input:** nums = \[3,4,4,5\]
**Output:** 3
**Explanation:** There are 3 square-free subsets in this example:
- The subset consisting of the 0th element \[3\]. The product of its elements is 3, which is a square-free integer.
- The subset consisting of the 3rd element \[5\]. The product of its elements is 5, which is a square-free integer.
- The subset consisting of 0th and 3rd elements \[3,5\]. The product of its elements is 15, which is a square-free integer.
It can be proven that there are no more than 3 square-free subsets in the given array.

**Example 2:**

**Input:** nums = \[1\]
**Output:** 1
**Explanation:** There is 1 square-free subset in this example:
- The subset consisting of the 0th element \[1\]. The product of its elements is 1, which is a square-free integer.
It can be proven that there is no more than 1 square-free subset in the given array.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 30`
Find the String with LCP

We define the `lcp` matrix of any **0-indexed** string `word` of `n` lowercase English letters as an `n x n` grid such that:

*   `lcp[i][j]` is equal to the length of the **longest common prefix** between the substrings `word[i,n-1]` and `word[j,n-1]`.

Given an `n x n` matrix `lcp`, return the alphabetically smallest string `word` that corresponds to `lcp`. If there is no such string, return an empty string.

A string `a` is lexicographically smaller than a string `b` (of the same length) if in the first position where `a` and `b` differ, string `a` has a letter that appears earlier in the alphabet than the corresponding letter in `b`. For example, `"aabd "` is lexicographically smaller than `"aaca "` because the first position they differ is at the third letter, and `'b'` comes before `'c'`.

**Example 1:**

**Input:** lcp = \[\[4,0,2,0\],\[0,3,0,1\],\[2,0,2,0\],\[0,1,0,1\]\]
**Output:**  "abab "
**Explanation:** lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is  "abab ".

**Example 2:**

**Input:** lcp = \[\[4,3,2,1\],\[3,3,2,1\],\[2,2,2,1\],\[1,1,1,1\]\]
**Output:**  "aaaa "
**Explanation:** lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is  "aaaa ". 

**Example 3:**

**Input:** lcp = \[\[4,3,2,1\],\[3,3,2,1\],\[2,2,2,1\],\[1,1,1,3\]\]
**Output:**  " "
**Explanation:** lcp\[3\]\[3\] cannot be equal to 3 since word\[3,...,3\] consists of only a single letter; Thus, no answer exists.

**Constraints:**

*   `1 <= n ==` `lcp.length ==` `lcp[i].length` `<= 1000`
*   `0 <= lcp[i][j] <= n`
Left and Right Sum Differences

Given a **0-indexed** integer array `nums`, find a **0-indexed** integer array `answer` where:

*   `answer.length == nums.length`.
*   `answer[i] = |leftSum[i] - rightSum[i]|`.

Where:

*   `leftSum[i]` is the sum of elements to the left of the index `i` in the array `nums`. If there is no such element, `leftSum[i] = 0`.
*   `rightSum[i]` is the sum of elements to the right of the index `i` in the array `nums`. If there is no such element, `rightSum[i] = 0`.

Return _the array_ `answer`.

**Example 1:**

**Input:** nums = \[10,4,8,3\]
**Output:** \[15,1,11,22\]
**Explanation:** The array leftSum is \[0,10,14,22\] and the array rightSum is \[15,11,3,0\].
The array answer is \[|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|\] = \[15,1,11,22\].

**Example 2:**

**Input:** nums = \[1\]
**Output:** \[0\]
**Explanation:** The array leftSum is \[0\] and the array rightSum is \[0\].
The array answer is \[|0 - 0|\] = \[0\].

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 105`
Find the Divisibility Array of a String

You are given a **0-indexed** string `word` of length `n` consisting of digits, and a positive integer `m`.

The **divisibility array** `div` of `word` is an integer array of length `n` such that:

*   `div[i] = 1` if the **numeric value** of `word[0,...,i]` is divisible by `m`, or
*   `div[i] = 0` otherwise.

Return _the divisibility array of_ `word`.

**Example 1:**

**Input:** word =  "998244353 ", m = 3
**Output:** \[1,1,0,0,0,1,1,0,0\]
**Explanation:** There are only 4 prefixes that are divisible by 3:  "9 ",  "99 ",  "998244 ", and  "9982443 ".

**Example 2:**

**Input:** word =  "1010 ", m = 10
**Output:** \[0,1,0,1\]
**Explanation:** There are only 2 prefixes that are divisible by 10:  "10 ", and  "1010 ".

**Constraints:**

*   `1 <= n <= 105`
*   `word.length == n`
*   `word` consists of digits from `0` to `9`
*   `1 <= m <= 109`
Minimum Time to Visit a Cell In a Grid

You are given a `m x n` matrix `grid` consisting of **non-negative** integers where `grid[row][col]` represents the **minimum** time required to be able to visit the cell `(row, col)`, which means you can visit the cell `(row, col)` only when the time you visit it is greater than or equal to `grid[row][col]`.

You are standing in the **top-left** cell of the matrix in the `0th` second, and you must move to **any** adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.

Return _the **minimum** time required in which you can visit the bottom-right cell of the matrix_. If you cannot visit the bottom-right cell, then return `-1`.

**Example 1:**

**Input:** grid = \[\[0,1,3,2\],\[5,1,2,5\],\[4,3,8,6\]\]
**Output:** 7
**Explanation:** One of the paths that we can take is the following:
- at t = 0, we are on the cell (0,0).
- at t = 1, we move to the cell (0,1). It is possible because grid\[0\]\[1\] <= 1.
- at t = 2, we move to the cell (1,1). It is possible because grid\[1\]\[1\] <= 2.
- at t = 3, we move to the cell (1,2). It is possible because grid\[1\]\[2\] <= 3.
- at t = 4, we move to the cell (1,1). It is possible because grid\[1\]\[1\] <= 4.
- at t = 5, we move to the cell (1,2). It is possible because grid\[1\]\[2\] <= 5.
- at t = 6, we move to the cell (1,3). It is possible because grid\[1\]\[3\] <= 6.
- at t = 7, we move to the cell (2,3). It is possible because grid\[2\]\[3\] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.

**Example 2:**

**Input:** grid = \[\[0,2,4\],\[3,2,1\],\[1,0,4\]\]
**Output:** -1
**Explanation:** There is no path from the top left to the bottom-right cell.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `2 <= m, n <= 1000`
*   `4 <= m * n <= 105`
*   `0 <= grid[i][j] <= 105`
*   `grid[0][0] == 0`

.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0; } .spoiler {overflow:hidden;} .spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;} .spoilerbutton\[value="Show Message"\] + .spoiler > div {margin-top:-500%;} .spoilerbutton\[value="Hide Message"\] + .spoiler {padding:5px;}
Split With Minimum Sum

Given a positive integer `num`, split it into two non-negative integers `num1` and `num2` such that:

*   The concatenation of `num1` and `num2` is a permutation of `num`.
    *   In other words, the sum of the number of occurrences of each digit in `num1` and `num2` is equal to the number of occurrences of that digit in `num`.
*   `num1` and `num2` can contain leading zeros.

Return _the **minimum** possible sum of_ `num1` _and_ `num2`.

**Notes:**

*   It is guaranteed that `num` does not contain any leading zeros.
*   The order of occurrence of the digits in `num1` and `num2` may differ from the order of occurrence of `num`.

**Example 1:**

**Input:** num = 4325
**Output:** 59
**Explanation:** We can split 4325 so that `num1` is 24 and num2 `is` 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.

**Example 2:**

**Input:** num = 687
**Output:** 75
**Explanation:** We can split 687 so that `num1` is 68 and `num2` is 7, which would give an optimal sum of 75.

**Constraints:**

*   `10 <= num <= 109`
Count Total Number of Colored Cells

There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer `n`, indicating that you must do the following routine for `n` minutes:

*   At the first minute, color **any** arbitrary unit cell blue.
*   Every minute thereafter, color blue **every** uncolored cell that touches a blue cell.

Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.

Return _the number of **colored cells** at the end of_ `n` _minutes_.

**Example 1:**

**Input:** n = 1
**Output:** 1
**Explanation:** After 1 minute, there is only 1 blue cell, so we return 1.

**Example 2:**

**Input:** n = 2
**Output:** 5
**Explanation:** After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5. 

**Constraints:**

*   `1 <= n <= 105`