Huahua’s Tech Road

花花酱 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;

}

};

花花酱 LeetCode 2177. Find Three Consecutive Integers That Sum to a Given Number

By zxi on March 4, 2022

Given an integer num, return three consecutive integers (as a sorted array) that sum to num. If num cannot be expressed as the sum of three consecutive integers, return an empty array.

Example 1:

Input: num = 33
Output: [10,11,12]
Explanation: 33 can be expressed as 10 + 11 + 12 = 33.
10, 11, 12 are 3 consecutive integers, so we return [10, 11, 12].

Example 2:

Input: num = 4
Output: []
Explanation: There is no way to express 4 as the sum of 3 consecutive integers.

Constraints:

0 <= num <= 10¹⁵

Solution: Math

(x / 3 – 1) + (x / 3) + (x / 3 + 1) == 3x == num, num must be divisible by 3.

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> sumOfThree(long long num) {

if (num % 3) return {};

return {num / 3 - 1, num / 3, num / 3 + 1};

}

};

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

1 <= nums.length <= 100
1 <= nums[i], k <= 100

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

ans += (nums[i] == nums[j]) && (i * j % k == 0);

return ans;

}

};

花花酱 LeetCode 2183. Count Array Pairs Divisible by K

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) such that:

0 <= i < j <= n - 1 and
nums[i] * nums[j] is divisible by k.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 7
Explanation: 
The 7 pairs of indices whose corresponding products are divisible by 2 are
(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), and (3, 4).
Their products are 2, 4, 6, 8, 10, 12, and 20 respectively.
Other pairs such as (0, 2) and (2, 4) have products 3 and 15 respectively, which are not divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 5
Output: 0
Explanation: There does not exist any pair of indices whose corresponding product is divisible by 5.

Constraints:

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

Solution: Math

a * b % k == 0 <=> gcd(a, k) * gcd(b, k) == 0

Use a counter of gcd(x, k) so far to compute the number of pairs.

Time complexity: O(n*f), where f is the number of gcds, f <= 128 for x <= 1e5
Space complexity: O(f)

C++

// Author: Huahua

class Solution {

public:

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

unordered_map<int, int> m;

long long ans = 0;

for (int x : nums) {

long long d1 = gcd(x, k);

for (const auto& [d2, c] : m)

if (d1 * d2 % k == 0) ans += c;

++m[d1];

}

return ans;

}

};

花花酱 LeetCode 2182. Construct String With Repeat Limit

By zxi on March 3, 2022

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2:

Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints:

1 <= repeatLimit <= s.length <= 10⁵
s consists of lowercase English letters.

Solution: Greedy

Adding one letter at a time, find the largest one that can be used.

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

C++

// Author: Huahua

class Solution {

public:

string repeatLimitedString(string s, int repeatLimit) {

vector<int> m(26);

for (char c : s) ++m[c - 'a'];

string ans;

int count = 0;

int last = -1;

while (true) {

bool found = false;

for (int i = 25; i >= 0 && !found; --i)

if (m[i] && (count < repeatLimit || last != i)) {

ans += 'a' + i;

count = (last == i) * count + 1;

--m[i];

last = i;

found = true;

}

if (!found) break;

}

return ans;

}

};

Huahua's Tech Road

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

Solution: Greedy

C++

花花酱 LeetCode 2177. Find Three Consecutive Integers That Sum to a Given Number

Solution: Math

C++

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

Solution: Brute Force

C++

花花酱 LeetCode 2183. Count Array Pairs Divisible by K

Solution: Math

C++

花花酱 LeetCode 2182. Construct String With Repeat Limit

Solution: Greedy

C++