Posts published in “Uncategorized”

花花酱 LeetCode 2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

By zxi on October 29, 2023

You are given two arrays nums1 and nums2 consisting of positive integers.

You have to replace all the 0‘s in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.

Return the minimum equal sum you can obtain, or -1 if it is impossible.

Example 1:

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: We can replace 0's in the following way:
- Replace the two 0's in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4].
- Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1].
Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.

Example 2:

Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: It is impossible to make the sum of both arrays equal.

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
0 <= nums1[i], nums2[i] <= 10⁶

Solution: A few cases

Calculate the sum of number of zeros of each array as (s1, z1), (s2, z2). There are a few cases:

z1 == z2 == 0, there is no way to change, just check s1 == s2.
z1 == 0, z1 != 0 or z2 == 0, z1 != 0. Need to at least increase the sum by number of zeros, check s1 + z1 <= s2 / s2 + z2 <= s1
z1 != 0, z2 != 0, the min sum is max(s1 + z1, s2 + z2)

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

C++

// Author: Huahua

class Solution {

public:

long long minSum(vector<int>& nums1, vector<int>& nums2) {

auto getSumAndZeros = [](const vector<int>& nums) {

long long sum = 0;

long long zeros = 0;

for (int x : nums) {

sum += x;

zeros += x == 0;

}

return pair{sum, zeros};

};

auto [s1, z1] = getSumAndZeros(nums1);

auto [s2, z2] = getSumAndZeros(nums2);

if (z1 == 0 && z2 == 0) {

return s1 == s2 ? s1 : -1;

} else if (z1 == 0) {

return s2 + z2 <= s1 ? s1 : -1;

} else if (z2 == 0) {

return s1 + z1 <= s2 ? s2 : -1;

} else {

return max(s1 + z1, s2 + z2);

}

return -1;

}

};

花花酱 LeetCode 2917. Find the K-or of an Array

By zxi on October 29, 2023

You are given a 0-indexed integer array nums, and an integer k.

The K-or of nums is a non-negative integer that satisfies the following:

The i^th bit is set in the K-or if and only if there are at least k elements of nums in which bit i is set.

Return the K-or of nums.

Note that a bit i is set in x if (2ⁱ AND x) == 2ⁱ, where AND is the bitwise AND operator.

Example 1:

Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation: Bit 0 is set at nums[0], nums[2], nums[4], and nums[5].
Bit 1 is set at nums[0], and nums[5].
Bit 2 is set at nums[0], nums[1], and nums[5].
Bit 3 is set at nums[1], nums[2], nums[3], nums[4], and nums[5].
Only bits 0 and 3 are set in at least k elements of the array, and bits i >= 4 are not set in any of the array's elements. Hence, the answer is 2^0 + 2^3 = 9.

Example 2:

Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: Since k == 6 == nums.length, the 6-or of the array is equal to the bitwise AND of all its elements. Hence, the answer is 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0.

Example 3:

Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: Since k == 1, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15.

Constraints:

1 <= nums.length <= 50
0 <= nums[i] < 2³¹
1 <= k <= nums.length

Solution: Bit Operation

Enumerate every bit and enumerate every number.

Time complexity: O(31 * n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findKOr(vector<int>& nums, int k) {

int ans = 0;

for (int i = 0; i < 31; ++i) {

int count = 0;

for (int x : nums)

if (x >> i & 1) ++count;

if (count >= k) ans |= 1 << i;

}

return ans;

}

};

花花酱 LeetCode 2666. Allow One Function Call

By zxi on May 7, 2023

Given a function fn, return a new function that is identical to the original function except that it ensures fn is called at most once.

The first time the returned function is called, it should return the same result as fn.
Every subsequent time it is called, it should return undefined.

Example 1:

Input: fn = (a,b,c) => (a + b + c), calls = [[1,2,3],[2,3,6]]
Output: [{"calls":1,"value":6}]
Explanation:
const onceFn = once(fn);
onceFn(1, 2, 3); // 6
onceFn(2, 3, 6); // undefined, fn was not called

Example 2:

Input: fn = (a,b,c) => (a * b * c), calls = [[5,7,4],[2,3,6],[4,6,8]]
Output: [{"calls":1,"value":140}]
Explanation:
const onceFn = once(fn);
onceFn(5, 7, 4); // 140
onceFn(2, 3, 6); // undefined, fn was not called
onceFn(4, 6, 8); // undefined, fn was not called

Constraints:

1 <= calls.length <= 10
1 <= calls[i].length <= 100
2 <= JSON.stringify(calls).length <= 1000

Solution:

JavaScript

// Author: Huahua

/**

* @param {Function} fn

* @return {Function}

var once = function(fn) {

this.called = false;

return function(...args){

if (this.called === false) {

this.called = true;

return fn(...args);

} else {

return undefined;

}

};

花花酱 LeetCode 2641. Cousins in Binary Tree II

By zxi on April 29, 2023

Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins’ values.

Two nodes of a binary tree are cousins if they have the same depth with different parents.

Return the root of the modified tree.

Note that the depth of a node is the number of edges in the path from the root node to it.

Example 1:

Input: root = [5,4,9,1,10,null,7]
Output: [0,0,0,7,7,null,11]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 5 does not have any cousins so its sum is 0.
- Node with value 4 does not have any cousins so its sum is 0.
- Node with value 9 does not have any cousins so its sum is 0.
- Node with value 1 has a cousin with value 7 so its sum is 7.
- Node with value 10 has a cousin with value 7 so its sum is 7.
- Node with value 7 has cousins with values 1 and 10 so its sum is 11.

Example 2:

Input: root = [3,1,2]
Output: [0,0,0]
Explanation: The diagram above shows the initial binary tree and the binary tree after changing the value of each node.
- Node with value 3 does not have any cousins so its sum is 0.
- Node with value 1 does not have any cousins so its sum is 0.
- Node with value 2 does not have any cousins so its sum is 0.

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁴

Solution: Level Order Sum

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

DFS, two passes

C++

// Author: Huahua

class Solution {

public:

TreeNode* replaceValueInTree(TreeNode* root) {

unordered_map<TreeNode*, int> parentSum;

parentSum[nullptr] = root->val;

vector<int> levelSums;

function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int depth) {

if (!node) return;

if (levelSums.size() <= depth) {

levelSums.push_back(0);

}

levelSums[depth] += node->val;

if (node->left) {

parentSum[node] += node->left->val;

dfs(node->left, depth + 1);

}

if (node->right) {

parentSum[node] += node->right->val;

dfs(node->right, depth + 1);

}

};

function<void(TreeNode*, TreeNode*, int)> dfs2 =

[&](TreeNode* node, TreeNode* p, int depth) {

if (!node) return;

node->val = levelSums[depth] - parentSum[p];

dfs2(node->left, node, depth + 1);

dfs2(node->right, node, depth + 1);

};

dfs(root, 0);

dfs2(root, nullptr, 0);

return root;

}

};

BFS, one+ pass

C++

// Author: Huahua

class Solution {

public:

TreeNode* replaceValueInTree(TreeNode* root) {

root->val = 0;

queue<TreeNode*> q({root});

while (!q.empty()) {

vector<TreeNode*> nodes;

int sum = 0;

for (int s = q.size(); s; --s) {

TreeNode* node = q.front(); q.pop();

nodes.push_back(node);

if (node->left) {

q.push(node->left);

sum += node->left->val;

}

if (node->right) {

q.push(node->right);

sum += node->right->val;

}

for (TreeNode* node : nodes) {

int val = sum - (node->left ? node->left->val : 0)

- (node->right ? node->right->val : 0);

if (node->left) node->left->val = val;

if (node->right) node->right->val = val;

}

return root;

}

};

花花酱 LeetCode 2523. Closest Prime Numbers in Range EP407

By zxi on December 31, 2022

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= nums1 < nums2 <= right .
nums1 and nums2 are both prime numbers.
nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10⁶

Solution: Sieve of Eratosthenes

Use Sieve of Eratosthenes to find all primes in range [0, right].

Check neighbor primes and find the best pair.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> closestPrimes(int left, int right) {

vector<int> primes(right + 1, 1);

primes[0] = primes[1] = 0;

for (int i = 2; i <= sqrt(right); ++i) {

if (!primes[i]) continue;

for (int x = i * i; x <= right; x += i)

primes[x] = 0;

}

vector<int> ans{-1,-1};

for (int i = left, last = -1, best = INT_MAX; i <= right; ++i) {

if (!primes[i]) continue;

if (last > 0 && i - last < best) {

best = i - last;

ans = {last, i};

}

last = i;

}

return ans;

}

};