Huahua’s Tech Road

花花酱 LeetCode 2974. Minimum Number Game

By zxi on January 8, 2024

You are given a 0-indexed integer array nums of even length and there is also an empty array arr. Alice and Bob decided to play a game where in every round Alice and Bob will do one move. The rules of the game are as follows:

Every round, first Alice will remove the minimum element from nums, and then Bob does the same.
Now, first Bob will append the removed element in the array arr, and then Alice does the same.
The game continues until nums becomes empty.

Return the resulting array arr.

Example 1:

Input: nums = [5,4,2,3]
Output: [3,2,5,4]
Explanation: In round one, first Alice removes 2 and then Bob removes 3. Then in arr firstly Bob appends 3 and then Alice appends 2. So arr = [3,2].
At the begining of round two, nums = [5,4]. Now, first Alice removes 4 and then Bob removes 5. Then both append in arr which becomes [3,2,5,4].

Example 2:

Input: nums = [2,5]
Output: [5,2]
Explanation: In round one, first Alice removes 2 and then Bob removes 5. Then in arr firstly Bob appends and then Alice appends. So arr = [5,2].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums.length % 2 == 0

Solution: Sort and Swap

Sort the array first and then swap the adjacent elements.

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

C++

class Solution {

public:

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

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

for (int i = 0; i < nums.size(); i += 2)

swap(nums[i], nums[i + 1]);

return nums;

}

};

花花酱 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 2829. Determine the Minimum Sum of a k-avoiding Array

By zxi on August 26, 2023

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

Constraints:

1 <= n, k <= 50

Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSum(int n, int k) {

int sum = 0;

unordered_set<int> s;

for (int i = 1; s.size() != n; ++i) {

if (s.count(k - i)) continue;

sum += i;

s.insert(i);

}

return sum;

}

};

花花酱 LeetCode 2828. Check if a String Is an Acronym of Words

By zxi on August 26, 2023

Given an array of strings words and a string s, determine if s is an acronym of words.

The string s is considered an acronym of words if it can be formed by concatenating the first character of each string in words in order. For example, "ab" can be formed from ["apple", "banana"], but it can’t be formed from ["bear", "aardvark"].

Return true if s is an acronym of words, and false otherwise.

Example 1:

Input: words = ["alice","bob","charlie"], s = "abc"
Output: true
Explanation: The first character in the words "alice", "bob", and "charlie" are 'a', 'b', and 'c', respectively. Hence, s = "abc" is the acronym.

Example 2:

Input: words = ["an","apple"], s = "a"
Output: false
Explanation: The first character in the words "an" and "apple" are 'a' and 'a', respectively. 
The acronym formed by concatenating these characters is "aa". 
Hence, s = "a" is not the acronym.

Example 3:

Input: words = ["never","gonna","give","up","on","you"], s = "ngguoy"
Output: true
Explanation: By concatenating the first character of the words in the array, we get the string "ngguoy". 
Hence, s = "ngguoy" is the acronym.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 10
1 <= s.length <= 100
words[i] and s consist of lowercase English letters.

Solution: Check the first letter of each word

No need to concatenate, just check the first letter of each word.

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

C++

// Author: Huahua

class Solution {

public:

bool isAcronym(vector<string>& words, string_view s) {

if (words.size() != s.size()) return false;

for (int i = 0; i < s.size(); ++i)

if (words[i][0] != s[i]) return false;

return true;

}

};

Huahua's Tech Road

花花酱 LeetCode 2974. Minimum Number Game

Solution: Sort and Swap

C++

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

Solution: A few cases

C++

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

Solution: Bit Operation

C++

花花酱 LeetCode 2829. Determine the Minimum Sum of a k-avoiding Array

Solution 1: Greedy + HashTable

C++

花花酱 LeetCode 2828. Check if a String Is an Acronym of Words

Solution: Check the first letter of each word

C++