Huahua’s Tech Road

花花酱 LeetCode 2197. Replace Non-Coprime Numbers in Array

By zxi on March 8, 2022

You are given an array of integers nums. Perform the following steps:

Find any two adjacent numbers in nums that are non-coprime.
If no such numbers are found, stop the process.
Otherwise, delete the two numbers and replace them with their LCM (Least Common Multiple).
Repeat this process as long as you keep finding two adjacent non-coprime numbers.

Return the final modified array. It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.

The test cases are generated such that the values in the final array are less than or equal to 10⁸.

Two values x and y are non-coprime if GCD(x, y) > 1 where GCD(x, y) is the Greatest Common Divisor of x and y.

Example 1:

Input: nums = [6,4,3,2,7,6,2]
Output: [12,7,6]
Explanation: 
- (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
- (12, 3) are non-coprime with LCM(12, 3) = 12. Now, nums = [12,2,7,6,2].
- (12, 2) are non-coprime with LCM(12, 2) = 12. Now, nums = [12,7,6,2].
- (6, 2) are non-coprime with LCM(6, 2) = 6. Now, nums = [12,7,6].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [12,7,6].
Note that there are other ways to obtain the same resultant array.

Example 2:

Input: nums = [2,2,1,1,3,3,3]
Output: [2,1,1,3]
Explanation: 
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3,3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2,2,1,1,3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2,1,1,3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2,1,1,3].
Note that there are other ways to obtain the same resultant array.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
The test cases are generated such that the values in the final array are less than or equal to 10⁸.

Solution: Stack

“””It can be shown that replacing adjacent non-coprime numbers in any arbitrary order will lead to the same result.”””

So that we can do it in one pass from left to right using a stack/vector.

Push the current number onto stack, and merge top two if they are not co-prime.

Time complexity: O(nlogm)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> replaceNonCoprimes(vector<int>& nums) {

vector<int> ans;

for (int x : nums) {

ans.push_back(x);

while (ans.size() > 1) {

const int n1 = ans[ans.size() - 1];

const int n2 = ans[ans.size() - 2];

const int d = gcd(n1, n2);

if (d == 1) break;

ans.pop_back();

ans.push_back(n1 / d * n2);

}

return ans;

}

};

花花酱 LeetCode 2196. Create Binary Tree From Descriptions

By zxi on March 8, 2022

You are given a 2D integer array descriptions where descriptions[i] = [parent_i, child_i, isLeft_i] indicates that parent_i is the parent of child_i in a binary tree of unique values. Furthermore,

If isLeft_i == 1, then child_i is the left child of parent_i.
If isLeft_i == 0, then child_i is the right child of parent_i.

Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid.

Example 1:

Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.

Example 2:

Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.

Constraints:

1 <= descriptions.length <= 10⁴
descriptions[i].length == 3
1 <= parent_i, child_i <= 10⁵
0 <= isLeft_i <= 1
The binary tree described by descriptions is valid.

Solution: Hashtable + Recursion

Use one hashtable to track the children of each node.
Use another hashtable to track the parent of each node.
Find the root who doesn’t have parent.
Build the tree recursively from root.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {

unordered_set<int> hasParent;

unordered_map<int, pair<int, int>> children;

for (const auto& d : descriptions) {

hasParent.insert(d[1]);

(d[2] ? children[d[0]].first : children[d[0]].second) = d[1];

}

int root = -1;

for (const auto& d : descriptions)

if (!hasParent.count(d[0])) root = d[0];

function<TreeNode*(int)> build = [&](int cur) -> TreeNode* {

if (!cur) return nullptr;

return new TreeNode(cur,

build(children[cur].first),

build(children[cur].second));

};

return build(root);

}

};

花花酱 LeetCode 2195. Append K Integers With Minimal Sum

By zxi on March 8, 2022

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.

Return the sum of the k integers appended to nums.

Example 1:

Input: nums = [1,4,25,10,25], k = 2
Output: 5
Explanation: The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.

Example 2:

Input: nums = [5,6], k = 6
Output: 25
Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁸

Solution: Greedy + Math, fill the gap

Sort all the numbers and remove duplicated ones, and fill the gap between two neighboring numbers.
e.g. [15, 3, 8, 8] => sorted = [3, 8, 15]
fill 0->3, 1,2, sum = ((0 + 1) + (3-1)) * (3-0-1) / 2 = 3
fill 3->8, 4, 5, 6, 7, sum = ((3 + 1) + (8-1)) * (8-3-1) / 2 = 22
fill 8->15, 9, 10, …, 14, …
fill 15->inf, 16, 17, …

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long minimalKSum(vector<int>& nums, int k) {

sort(begin(nums), end(nums));

long long ans = 0;

long long p = 0;

for (int c : nums) {

if (c == p) continue;

long long n = min((long long)k, c - p - 1);

ans += (p + 1 + p + n) * n / 2;

k -= n;

p = c;

}

ans += (p + 1 + p + k) * k / 2;

return ans;

}

};

花花酱 LeetCode 2194. Cells in a Range on an Excel Sheet

By zxi on March 8, 2022

A cell (r, c) of an excel sheet is represented as a string "<col><row>" where:

<col> denotes the column number c of the cell. It is represented by alphabetical letters.
- For example, the 1^st column is denoted by 'A', the 2^nd by 'B', the 3^rd by 'C', and so on.
<row> is the row number r of the cell. The r^th row is represented by the integer r.

You are given a string s in the format "<col1><row1>:<col2><row2>", where <col1> represents the column c1, <row1> represents the row r1, <col2> represents the column c2, and <row2> represents the row r2, such that r1 <= r2 and c1 <= c2.

Return the list of cells (x, y) such that r1 <= x <= r2 and c1 <= y <= c2. The cells should be represented as strings in the format mentioned above and be sorted in non-decreasing order first by columns and then by rows.

Example 1:

Input: s = "K1:L2"
Output: ["K1","K2","L1","L2"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrows denote the order in which the cells should be presented.

Example 2:

Input: s = "A1:F1"
Output: ["A1","B1","C1","D1","E1","F1"]
Explanation:
The above diagram shows the cells which should be present in the list.
The red arrow denotes the order in which the cells should be presented.

Constraints:

s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s consists of uppercase English letters, digits and ':'.

Solution: Brute Force

Time complexity: O((row2 – row1 + 1) * (col2 – col1 + 1))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> cellsInRange(string s) {

vector<string> ans;

for (char c = s[0]; c <= s[3]; ++c)

for (char r = s[1]; r <= s[4]; ++r)

ans.push_back(string{c, r});

return ans;

}

};

花花酱 LeetCode 2178. Maximum Split of Positive Even Integers

By zxi on March 4, 2022

You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.

For example, given finalSum = 12, the following splits are valid (unique positive even integers summing up to finalSum): (12), (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the numbers should be unique.

Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.

Example 1:

Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6].
Note that [2,6,4], [6,2,4], etc. are also accepted.

Example 2:

Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.

Example 3:

Input: finalSum = 28
Output: [6,8,2,12]
Explanation: The following are valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24). 
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.

Constraints:

1 <= finalSum <= 10¹⁰

Solution: Greedy

The get the maximum number of elements, we must use the smallest numbers.

[2, 4, 6, …, 2k, x], where x > 2k
let s = 2 + 4 + … + 2k, x = num – s
since num is odd and s is also odd, so thus x = num – s.

Time complexity: O(sqrt(num)) for constructing outputs.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<long long> maximumEvenSplit(long long finalSum) {

if (finalSum & 1) return {};

vector<long long> ans;

long long s = 0;

for (long long i = 2; s + i <= finalSum; s += i, i += 2)

ans.push_back(i);

ans.back() += (finalSum - s);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2197. Replace Non-Coprime Numbers in Array

Solution: Stack

C++

花花酱 LeetCode 2196. Create Binary Tree From Descriptions

Solution: Hashtable + Recursion

C++

花花酱 LeetCode 2195. Append K Integers With Minimal Sum

Solution: Greedy + Math, fill the gap

C++

花花酱 LeetCode 2194. Cells in a Range on an Excel Sheet

Solution: Brute Force

C++

花花酱 LeetCode 2178. Maximum Split of Positive Even Integers

Solution: Greedy

C++