bowang0911/leetcode huggingface dataset:
Minimum Flips in Binary Tree to Get Result

You are given the `root` of a **binary tree** with the following properties:

*   **Leaf nodes** have either the value `0` or `1`, representing `false` and `true` respectively.
*   **Non-leaf nodes** have either the value `2`, `3`, `4`, or `5`, representing the boolean operations `OR`, `AND`, `XOR`, and `NOT`, respectively.

You are also given a boolean `result`, which is the desired result of the **evaluation** of the `root` node.

The evaluation of a node is as follows:

*   If the node is a leaf node, the evaluation is the **value** of the node, i.e. `true` or `false`.
*   Otherwise, **evaluate** the node's children and **apply** the boolean operation of its value with the children's evaluations.

In one operation, you can **flip** a leaf node, which causes a `false` node to become `true`, and a `true` node to become `false`.

Return _the minimum number of operations that need to be performed such that the evaluation of_ `root` _yields_ `result`. It can be shown that there is always a way to achieve `result`.

A **leaf node** is a node that has zero children.

Note: `NOT` nodes have either a left child or a right child, but other non-leaf nodes have both a left child and a right child.

**Example 1:**

**Input:** root = \[3,5,4,2,null,1,1,1,0\], result = true
**Output:** 2
**Explanation:**
It can be shown that a minimum of 2 nodes have to be flipped to make the root of the tree
evaluate to true. One way to achieve this is shown in the diagram above.

**Example 2:**

**Input:** root = \[0\], result = false
**Output:** 0
**Explanation:**
The root of the tree already evaluates to false, so 0 nodes have to be flipped.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 105]`.
*   `0 <= Node.val <= 5`
*   `OR`, `AND`, and `XOR` nodes have `2` children.
*   `NOT` nodes have `1` child.
*   Leaf nodes have a value of `0` or `1`.
*   Non-leaf nodes have a value of `2`, `3`, `4`, or `5`.
Count Asterisks

You are given a string `s`, where every **two** consecutive vertical bars `'|'` are grouped into a **pair**. In other words, the 1st and 2nd `'|'` make a pair, the 3rd and 4th `'|'` make a pair, and so forth.

Return _the number of_ `'*'` _in_ `s`_, **excluding** the_ `'*'` _between each pair of_ `'|'`.

**Note** that each `'|'` will belong to **exactly** one pair.

**Example 1:**

**Input:** s =  "l|\*e\*et|c\*\*o|\*de| "
**Output:** 2
**Explanation:** The considered characters are underlined:  "l|\*e\*et|c\*\*o|\*de| ".
The characters between the first and second '|' are excluded from the answer.
Also, the characters between the third and fourth '|' are excluded from the answer.
There are 2 asterisks considered. Therefore, we return 2.

**Example 2:**

**Input:** s =  "iamprogrammer "
**Output:** 0
**Explanation:** In this example, there are no asterisks in s. Therefore, we return 0.

**Example 3:**

**Input:** s =  "yo|uar|e\*\*|b|e\*\*\*au|tifu|l "
**Output:** 5
**Explanation:** The considered characters are underlined:  "yo|uar|e\*\*|b|e\*\*\*au|tifu|l ". There are 5 asterisks considered. Therefore, we return 5.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists of lowercase English letters, vertical bars `'|'`, and asterisks `'*'`.
*   `s` contains an **even** number of vertical bars `'|'`.
Count Unreachable Pairs of Nodes in an Undirected Graph

You are given an integer `n`. There is an **undirected** graph with `n` nodes, numbered from `0` to `n - 1`. You are given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an **undirected** edge connecting nodes `ai` and `bi`.

Return _the **number of pairs** of different nodes that are **unreachable** from each other_.

**Example 1:**

**Input:** n = 3, edges = \[\[0,1\],\[0,2\],\[1,2\]\]
**Output:** 0
**Explanation:** There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

**Example 2:**

**Input:** n = 7, edges = \[\[0,2\],\[0,5\],\[2,4\],\[1,6\],\[5,4\]\]
**Output:** 14
**Explanation:** There are 14 pairs of nodes that are unreachable from each other:
\[\[0,1\],\[0,3\],\[0,6\],\[1,2\],\[1,3\],\[1,4\],\[1,5\],\[2,3\],\[2,6\],\[3,4\],\[3,5\],\[3,6\],\[4,6\],\[5,6\]\].
Therefore, we return 14.

**Constraints:**

*   `1 <= n <= 105`
*   `0 <= edges.length <= 2 * 105`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   There are no repeated edges.
Maximum XOR After Operations

You are given a **0-indexed** integer array `nums`. In one operation, select **any** non-negative integer `x` and an index `i`, then **update** `nums[i]` to be equal to `nums[i] AND (nums[i] XOR x)`.

Note that `AND` is the bitwise AND operation and `XOR` is the bitwise XOR operation.

Return _the **maximum** possible bitwise XOR of all elements of_ `nums` _after applying the operation **any number** of times_.

**Example 1:**

**Input:** nums = \[3,2,4,6\]
**Output:** 7
**Explanation:** Apply the operation with x = 4 and i = 3, num\[3\] = 6 AND (6 XOR 4) = 6 AND 2 = 2.
Now, nums = \[3, 2, 4, 2\] and the bitwise XOR of all the elements = 3 XOR 2 XOR 4 XOR 2 = 7.
It can be shown that 7 is the maximum possible bitwise XOR.
Note that other operations may be used to achieve a bitwise XOR of 7.

**Example 2:**

**Input:** nums = \[1,2,3,9,2\]
**Output:** 11
**Explanation:** Apply the operation zero times.
The bitwise XOR of all the elements = 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11.
It can be shown that 11 is the maximum possible bitwise XOR.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 108`
Number of Distinct Roll Sequences

You are given an integer `n`. You roll a fair 6-sided dice `n` times. Determine the total number of **distinct** sequences of rolls possible such that the following conditions are satisfied:

1.  The **greatest common divisor** of any **adjacent** values in the sequence is equal to `1`.
2.  There is **at least** a gap of `2` rolls between **equal** valued rolls. More formally, if the value of the `ith` roll is **equal** to the value of the `jth` roll, then `abs(i - j) > 2`.

Return _the **total number** of distinct sequences possible_. Since the answer may be very large, return it **modulo** `109 + 7`.

Two sequences are considered distinct if at least one element is different.

**Example 1:**

**Input:** n = 4
**Output:** 184
**Explanation:** Some of the possible sequences are (1, 2, 3, 4), (6, 1, 2, 3), (1, 2, 3, 1), etc.
Some invalid sequences are (1, 2, 1, 3), (1, 2, 3, 6).
(1, 2, 1, 3) is invalid since the first and third roll have an equal value and abs(1 - 3) = 2 (i and j are 1-indexed).
(1, 2, 3, 6) is invalid since the greatest common divisor of 3 and 6 = 3.
There are a total of 184 distinct sequences possible, so we return 184.

**Example 2:**

**Input:** n = 2
**Output:** 22
**Explanation:** Some of the possible sequences are (1, 2), (2, 1), (3, 2).
Some invalid sequences are (3, 6), (2, 4) since the greatest common divisor is not equal to 1.
There are a total of 22 distinct sequences possible, so we return 22.

**Constraints:**

*   `1 <= n <= 104`
Check if Matrix Is X-Matrix

A square matrix is said to be an **X-Matrix** if **both** of the following conditions hold:

1.  All the elements in the diagonals of the matrix are **non-zero**.
2.  All other elements are 0.

Given a 2D integer array `grid` of size `n x n` representing a square matrix, return `true` _if_ `grid` _is an X-Matrix_. Otherwise, return `false`.

**Example 1:**

**Input:** grid = \[\[2,0,0,1\],\[0,3,1,0\],\[0,5,2,0\],\[4,0,0,2\]\]
**Output:** true
**Explanation:** Refer to the diagram above. 
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0.
Thus, grid is an X-Matrix.

**Example 2:**

**Input:** grid = \[\[5,7,0\],\[0,3,1\],\[0,5,0\]\]
**Output:** false
**Explanation:** Refer to the diagram above.
An X-Matrix should have the green elements (diagonals) be non-zero and the red elements be 0.
Thus, grid is not an X-Matrix.

**Constraints:**

*   `n == grid.length == grid[i].length`
*   `3 <= n <= 100`
*   `0 <= grid[i][j] <= 105`
Count Number of Ways to Place Houses

There is a street with `n * 2` **plots**, where there are `n` plots on each side of the street. The plots on each side are numbered from `1` to `n`. On each plot, a house can be placed.

Return _the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street_. Since the answer may be very large, return it **modulo** `109 + 7`.

Note that if a house is placed on the `ith` plot on one side of the street, a house can also be placed on the `ith` plot on the other side of the street.

**Example 1:**

**Input:** n = 1
**Output:** 4
**Explanation:** 
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.

**Example 2:**

**Input:** n = 2
**Output:** 9
**Explanation:** The 9 possible arrangements are shown in the diagram above.

**Constraints:**

*   `1 <= n <= 104`
Maximum Score Of Spliced Array

You are given two **0-indexed** integer arrays `nums1` and `nums2`, both of length `n`.

You can choose two integers `left` and `right` where `0 <= left <= right < n` and **swap** the subarray `nums1[left...right]` with the subarray `nums2[left...right]`.

*   For example, if `nums1 = [1,2,3,4,5]` and `nums2 = [11,12,13,14,15]` and you choose `left = 1` and `right = 2`, `nums1` becomes `[1,**12,13**,4,5]` and `nums2` becomes `[11,**2,3**,14,15]`.

You may choose to apply the mentioned operation **once** or not do anything.

The **score** of the arrays is the **maximum** of `sum(nums1)` and `sum(nums2)`, where `sum(arr)` is the sum of all the elements in the array `arr`.

Return _the **maximum possible score**_.

A **subarray** is a contiguous sequence of elements within an array. `arr[left...right]` denotes the subarray that contains the elements of `nums` between indices `left` and `right` (**inclusive**).

**Example 1:**

**Input:** nums1 = \[60,60,60\], nums2 = \[10,90,10\]
**Output:** 210
**Explanation:** Choosing left = 1 and right = 1, we have nums1 = \[60,**90**,60\] and nums2 = \[10,**60**,10\].
The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.

**Example 2:**

**Input:** nums1 = \[20,40,20,70,30\], nums2 = \[50,20,50,40,20\]
**Output:** 220
**Explanation:** Choosing left = 3, right = 4, we have nums1 = \[20,40,20,**40,20**\] and nums2 = \[50,20,50,**70,30**\].
The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.

**Example 3:**

**Input:** nums1 = \[7,11,13\], nums2 = \[1,1,1\]
**Output:** 31
**Explanation:** We choose not to swap any subarray.
The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.

**Constraints:**

*   `n == nums1.length == nums2.length`
*   `1 <= n <= 105`
*   `1 <= nums1[i], nums2[i] <= 104`
Minimum Score After Removals on a Tree

There is an undirected connected tree with `n` nodes labeled from `0` to `n - 1` and `n - 1` edges.

You are given a **0-indexed** integer array `nums` of length `n` where `nums[i]` represents the value of the `ith` node. You are also given a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

Remove two **distinct** edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:

1.  Get the XOR of all the values of the nodes for **each** of the three components respectively.
2.  The **difference** between the **largest** XOR value and the **smallest** XOR value is the **score** of the pair.

*   For example, say the three components have the node values: `[4,5,7]`, `[1,9]`, and `[3,3,3]`. The three XOR values are `4 ^ 5 ^ 7 = **6**`, `1 ^ 9 = **8**`, and `3 ^ 3 ^ 3 = **3**`. The largest XOR value is `8` and the smallest XOR value is `3`. The score is then `8 - 3 = 5`.

Return _the **minimum** score of any possible pair of edge removals on the given tree_.

**Example 1:**

**Input:** nums = \[1,5,5,4,11\], edges = \[\[0,1\],\[1,2\],\[1,3\],\[3,4\]\]
**Output:** 9
**Explanation:** The diagram above shows a way to make a pair of removals.
- The 1st component has nodes \[1,3,4\] with values \[5,4,11\]. Its XOR value is 5 ^ 4 ^ 11 = 10.
- The 2nd component has node \[0\] with value \[1\]. Its XOR value is 1 = 1.
- The 3rd component has node \[2\] with value \[5\]. Its XOR value is 5 = 5.
The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9.
It can be shown that no other pair of removals will obtain a smaller score than 9.

**Example 2:**

**Input:** nums = \[5,5,2,4,4,2\], edges = \[\[0,1\],\[1,2\],\[5,2\],\[4,3\],\[1,3\]\]
**Output:** 0
**Explanation:** The diagram above shows a way to make a pair of removals.
- The 1st component has nodes \[3,4\] with values \[4,4\]. Its XOR value is 4 ^ 4 = 0.
- The 2nd component has nodes \[1,0\] with values \[5,5\]. Its XOR value is 5 ^ 5 = 0.
- The 3rd component has nodes \[2,5\] with values \[2,2\]. Its XOR value is 2 ^ 2 = 0.
The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0.
We cannot obtain a smaller score than 0.

**Constraints:**

*   `n == nums.length`
*   `3 <= n <= 1000`
*   `1 <= nums[i] <= 108`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   `edges` represents a valid tree.
Find Minimum Time to Finish All Jobs II

You are given two **0-indexed** integer arrays `jobs` and `workers` of **equal** length, where `jobs[i]` is the amount of time needed to complete the `ith` job, and `workers[j]` is the amount of time the `jth` worker can work each day.

Each job should be assigned to **exactly** one worker, such that each worker completes **exactly** one job.

Return _the **minimum** number of days needed to complete all the jobs after assignment._

**Example 1:**

**Input:** jobs = \[5,2,4\], workers = \[1,7,5\]
**Output:** 2
**Explanation:**
- Assign the 2nd worker to the 0th job. It takes them 1 day to finish the job.
- Assign the 0th worker to the 1st job. It takes them 2 days to finish the job.
- Assign the 1st worker to the 2nd job. It takes them 1 day to finish the job.
It takes 2 days for all the jobs to be completed, so return 2.
It can be proven that 2 days is the minimum number of days needed.

**Example 2:**

**Input:** jobs = \[3,18,15,9\], workers = \[6,5,1,3\]
**Output:** 3
**Explanation:**
- Assign the 2nd worker to the 0th job. It takes them 3 days to finish the job.
- Assign the 0th worker to the 1st job. It takes them 3 days to finish the job.
- Assign the 1st worker to the 2nd job. It takes them 3 days to finish the job.
- Assign the 3rd worker to the 3rd job. It takes them 3 days to finish the job.
It takes 3 days for all the jobs to be completed, so return 3.
It can be proven that 3 days is the minimum number of days needed.

**Constraints:**

*   `n == jobs.length == workers.length`
*   `1 <= n <= 105`
*   `1 <= jobs[i], workers[i] <= 105`
Decode the Message

You are given the strings `key` and `message`, which represent a cipher key and a secret message, respectively. The steps to decode `message` are as follows:

1.  Use the **first** appearance of all 26 lowercase English letters in `key` as the **order** of the substitution table.
2.  Align the substitution table with the regular English alphabet.
3.  Each letter in `message` is then **substituted** using the table.
4.  Spaces `' '` are transformed to themselves.

*   For example, given `key = "**hap**p**y** **bo**y "` (actual key would have **at least one** instance of each letter in the alphabet), we have the partial substitution table of (`'h' -> 'a'`, `'a' -> 'b'`, `'p' -> 'c'`, `'y' -> 'd'`, `'b' -> 'e'`, `'o' -> 'f'`).

Return _the decoded message_.

**Example 1:**

**Input:** key =  "the quick brown fox jumps over the lazy dog ", message =  "vkbs bs t suepuv "
**Output:**  "this is a secret "
**Explanation:** The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in  "**the** **quick** **brown** **f**o**x** **j**u**mps** o**v**er the **lazy** **d**o**g** ".

**Example 2:**

**Input:** key =  "eljuxhpwnyrdgtqkviszcfmabo ", message =  "zwx hnfx lqantp mnoeius ycgk vcnjrdb "
**Output:**  "the five boxing wizards jump quickly "
**Explanation:** The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in  "**eljuxhpwnyrdgtqkviszcfmabo** ".

**Constraints:**

*   `26 <= key.length <= 2000`
*   `key` consists of lowercase English letters and `' '`.
*   `key` contains every letter in the English alphabet (`'a'` to `'z'`) **at least once**.
*   `1 <= message.length <= 2000`
*   `message` consists of lowercase English letters and `' '`.
Spiral Matrix IV

You are given two integers `m` and `n`, which represent the dimensions of a matrix.

You are also given the `head` of a linked list of integers.

Generate an `m x n` matrix that contains the integers in the linked list presented in **spiral** order **(clockwise)**, starting from the **top-left** of the matrix. If there are remaining empty spaces, fill them with `-1`.

Return _the generated matrix_.

**Example 1:**

**Input:** m = 3, n = 5, head = \[3,0,2,6,8,1,7,9,4,2,5,5,0\]
**Output:** \[\[3,0,2,6,8\],\[5,0,-1,-1,1\],\[5,2,4,9,7\]\]
**Explanation:** The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.

**Example 2:**

**Input:** m = 1, n = 4, head = \[0,1,2\]
**Output:** \[\[0,1,2,-1\]\]
**Explanation:** The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

**Constraints:**

*   `1 <= m, n <= 105`
*   `1 <= m * n <= 105`
*   The number of nodes in the list is in the range `[1, m * n]`.
*   `0 <= Node.val <= 1000`
Number of People Aware of a Secret

On day `1`, one person discovers a secret.

You are given an integer `delay`, which means that each person will **share** the secret with a new person **every day**, starting from `delay` days after discovering the secret. You are also given an integer `forget`, which means that each person will **forget** the secret `forget` days after discovering it. A person **cannot** share the secret on the same day they forgot it, or on any day afterwards.

Given an integer `n`, return _the number of people who know the secret at the end of day_ `n`. Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 6, delay = 2, forget = 4
**Output:** 5
**Explanation:**
Day 1: Suppose the first person is named A. (1 person)
Day 2: A is the only person who knows the secret. (1 person)
Day 3: A shares the secret with a new person, B. (2 people)
Day 4: A shares the secret with a new person, C. (3 people)
Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people)
Day 6: B shares the secret with E, and C shares the secret with F. (5 people)

**Example 2:**

**Input:** n = 4, delay = 1, forget = 3
**Output:** 6
**Explanation:**
Day 1: The first person is named A. (1 person)
Day 2: A shares the secret with B. (2 people)
Day 3: A and B share the secret with 2 new people, C and D. (4 people)
Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)

**Constraints:**

*   `2 <= n <= 1000`
*   `1 <= delay < forget <= n`
Number of Increasing Paths in a Grid

You are given an `m x n` integer matrix `grid`, where you can move from a cell to any adjacent cell in all `4` directions.

Return _the number of **strictly** **increasing** paths in the grid such that you can start from **any** cell and end at **any** cell._ Since the answer may be very large, return it **modulo** `109 + 7`.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

**Example 1:**

**Input:** grid = \[\[1,1\],\[3,4\]\]
**Output:** 8
**Explanation:** The strictly increasing paths are:
- Paths with length 1: \[1\], \[1\], \[3\], \[4\].
- Paths with length 2: \[1 -> 3\], \[1 -> 4\], \[3 -> 4\].
- Paths with length 3: \[1 -> 3 -> 4\].
The total number of paths is 4 + 3 + 1 = 8.

**Example 2:**

**Input:** grid = \[\[1\],\[2\]\]
**Output:** 3
**Explanation:** The strictly increasing paths are:
- Paths with length 1: \[1\], \[2\].
- Paths with length 2: \[1 -> 2\].
The total number of paths is 2 + 1 = 3.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 1000`
*   `1 <= m * n <= 105`
*   `1 <= grid[i][j] <= 105`
Valid Palindrome IV

You are given a **0-indexed** string `s` consisting of only lowercase English letters. In one operation, you can change **any** character of `s` to any **other** character.

Return `true` _if you can make_ `s` _a palindrome after performing **exactly** one or two operations, or return_ `false` _otherwise._

**Example 1:**

**Input:** s =  "abcdba "
**Output:** true
**Explanation:** One way to make s a palindrome using 1 operation is:
- Change s\[2\] to 'd'. Now, s =  "abddba ".
One operation could be performed to make s a palindrome so return true.

**Example 2:**

**Input:** s =  "aa "
**Output:** true
**Explanation:** One way to make s a palindrome using 2 operations is:
- Change s\[0\] to 'b'. Now, s =  "ba ".
- Change s\[1\] to 'b'. Now, s =  "bb ".
Two operations could be performed to make s a palindrome so return true.

**Example 3:**

**Input:** s =  "abcdef "
**Output:** false
**Explanation:** It is not possible to make s a palindrome using one or two operations so return false.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists only of lowercase English letters.
Evaluate Boolean Binary Tree

You are given the `root` of a **full binary tree** with the following properties:

*   **Leaf nodes** have either the value `0` or `1`, where `0` represents `False` and `1` represents `True`.
*   **Non-leaf nodes** have either the value `2` or `3`, where `2` represents the boolean `OR` and `3` represents the boolean `AND`.

The **evaluation** of a node is as follows:

*   If the node is a leaf node, the evaluation is the **value** of the node, i.e. `True` or `False`.
*   Otherwise, **evaluate** the node's two children and **apply** the boolean operation of its value with the children's evaluations.

Return _the boolean result of **evaluating** the_ `root` _node._

A **full binary tree** is a binary tree where each node has either `0` or `2` children.

A **leaf node** is a node that has zero children.

**Example 1:**

**Input:** root = \[2,1,3,null,null,0,1\]
**Output:** true
**Explanation:** The above diagram illustrates the evaluation process.
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.

**Example 2:**

**Input:** root = \[0\]
**Output:** false
**Explanation:** The root node is a leaf node and it evaluates to false, so we return false.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 1000]`.
*   `0 <= Node.val <= 3`
*   Every node has either `0` or `2` children.
*   Leaf nodes have a value of `0` or `1`.
*   Non-leaf nodes have a value of `2` or `3`.