Huahua’s Tech Road

花花酱 LeetCode 1922. Count Good Numbers

By zxi on December 25, 2021

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10⁹ + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

Constraints:

1 <= n <= 10¹⁵

Solution: Fast Power

Easy to see that f(n) = (4 + (n & 1)) * f(n – 1), f(1) = 5

However, since n is huge, we need to rewrite f(n) as 4^n/2 * 5^(n+1)/2 and use fast power to compute it.

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

C++

// Author: Huahua

constexpr int kMod = 1e9 + 7;

long long modPow(long long base, long long n) {

long long ans = 1;

while (n) {

if (n & 1) ans = (ans * base) % kMod;

base = (base * base) % kMod;

n >>= 1;

}

return ans;

}

class Solution {

public:

int countGoodNumbers(long long n) {

return (modPow(4, n / 2) * modPow(5, (n + 1) / 2)) % kMod;

}

};

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

By zxi on December 25, 2021

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the i^th monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the i^th monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Constraints:

n == dist.length == speed.length
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Solution: Greedy

Sort by arrival time, and see how many we can eliminate.

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

C++

// Author: Huahua

class Solution {

public:

int eliminateMaximum(vector<int>& dist, vector<int>& speed) {

const int n = dist.size();

vector<int> t(n);

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

t[i] = (dist[i] + speed[i] - 1) / speed[i];

sort(begin(t), end(t));

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

if (t[i] <= i) return i;

return n;

}

};

花花酱 LeetCode 1920. Build Array from Permutation

By zxi on December 25, 2021

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

Example 1:

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows: 
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

Example 2:

Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] < nums.length
The elements in nums are distinct.

Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

Solution 1: Straight forward

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> ans(nums);

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

ans[i] = nums[nums[i]];

return ans;

}

};

Solution 2: Follow up: Inplace Encoding

Since nums[i] <= 1000, we can use low 16 bit to store the original value and high 16 bit for new value.

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

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

nums[i] |= (nums[nums[i]] & 0xffff) << 16;

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

nums[i] >>= 16;

return nums;

}

};

花花酱 LeetCode 1915. Number of Wonderful Substrings

By zxi on December 25, 2021

A wonderful string is a string where at most one letter appears an odd number of times.

For example, "ccjjc" and "abab" are wonderful, but "ab" is not.

Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

Example 2:

Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

Example 3:

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"

Constraints:

1 <= word.length <= 10⁵
word consists of lowercase English letters from 'a' to 'j'.

Solution: Prefix Bitmask + Hashtable

Similar to 花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts, we use a bitmask to represent the occurrence (odd or even) of each letter and use a hashtable to store the frequency of each bitmask seen so far.

1. “0000000000” means all letters occur even times.
2. “0000000101” means all letters occur even times expect letter ‘a’ and ‘c’ that occur odd times.

We scan the word from left to right and update the bitmask: bitmask ^= (1 << (c-‘a’)).
However, the bitmask only represents the state of the prefix, i.e. word[0:i], then how can we count substrings? The answer is hashtable. If the same bitmask occurs c times before, which means there are c indices that word[0~j1], word[0~j2], …, word[0~jc] have the same state as word[0~i] that means for word[j1+1~i], word[j2+1~i], …, word[jc+1~i], all letters occurred even times.
For the “at most one odd” case, we toggle each bit of the bitmask and check how many times it occurred before.

ans += freq[mask] + sum(freq[mask ^ (1 << i)] for i in range(k))

Time complexity: O(n*k)
Space complexity: O(2^k)
where k = j – a + 1 = 10

C++

// Author: Huahua

class Solution {

public:

long long wonderfulSubstrings(string word) {

constexpr int l = 'j' - 'a' + 1;

vector<int> count(1 << l);

count[0] = 1;

int mask = 0;

long long ans = 0;

for (char c : word) {

mask ^= 1 << (c - 'a');

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

ans += count[mask ^ (1 << i)]; // one odd.

ans += count[mask]++; // all even.

}

return ans;

}

};

花花酱 LeetCode 1913. Maximum Product Difference Between Two Pairs

By zxi on December 24, 2021

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

Example 1:

Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.

Example 2:

Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.

Constraints:

4 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Solution: Greedy

Since all the numbers are positive, we just need to find the largest two numbers as the first pair and smallest two numbers are the second pair.

Time complexity: O(nlogn) / sorting, O(n) / finding min/max elements.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProductDifference(vector<int>& nums) {

const int n = nums.size();

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

return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];

}

};

Python3

# Author: Huahua

class Solution:

def maxProductDifference(self, nums: List[int]) -> int:

nums.sort()

return nums[-1] * nums[-2] - nums[0] * nums[1]

Huahua's Tech Road

花花酱 LeetCode 1922. Count Good Numbers

Solution: Fast Power

C++

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

Solution: Greedy

C++

花花酱 LeetCode 1920. Build Array from Permutation

Solution 1: Straight forward

C++

Solution 2: Follow up: Inplace Encoding

C++

花花酱 LeetCode 1915. Number of Wonderful Substrings

Solution: Prefix Bitmask + Hashtable

C++

花花酱 LeetCode 1913. Maximum Product Difference Between Two Pairs

Solution: Greedy

C++

Python3