Huahua’s Tech Road

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

By zxi on August 4, 2021

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 10⁹+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

Constraints:

1 <= n <= 1000
1 <= k <= n

Solution: DP

dp(n, k) = dp(n – 1, k – 1) + (n-1) * dp(n-1, k)

Time complexity: O(n*k)
Space complexity: O(n*k) -> O(k)

C++

// Author: Huahua

class Solution {

public:

int rearrangeSticks(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(k + 1));

for (int j = 1; j <= k; ++j) {

dp[j][j] = 1;

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

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod;

}

return dp[n][k];

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None)

def rearrangeSticks(self, n: int, k: int) -> int:

if k == 0: return 0

if k == n or n <= 2: return 1

return (self.rearrangeSticks(n - 1, k - 1) +

(n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7)

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

By zxi on August 4, 2021

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]
Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4] 
findSumPairs.count(8); // return 2; pairs (5,2), (5,4) make 3 + 5 
findSumPairs.count(4); // return 1; pair (5,0) makes 3 + 1 
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4] 
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4] 
findSumPairs.count(7); // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Solution: HashTable

Note nums1 and nums2 are unbalanced. Brute force method will take O(m*n) = O(10³*10⁵) = O(10⁸) for each count call which will TLE. We could use a hashtable to store the counts of elements from nums2, and only iterate over nums1 to reduce the time complexity.

Time complexity:

init: O(m) + O(n)
add: O(1)
count: O(m)

Total time is less than O(10⁶)

Space complexity: O(m + n)

C++

// Author: Huahua

class FindSumPairs {

public:

FindSumPairs(vector<int>& nums1,

vector<int>& nums2): nums1_(nums1), nums2_(nums2) {

for (int x : nums2_) ++freq_[x];

}

void add(int index, int val) {

if (--freq_[nums2_[index]] == 0)

freq_.erase(nums2_[index]);

++freq_[nums2_[index] += val];

}

int count(int tot) {

int ans = 0;

for (int a : nums1_) {

auto it = freq_.find(tot - a);

if (it != freq_.end()) ans += it->second;

}

return ans;

}

private:

vector<int> nums1_;

vector<int> nums2_;

unordered_map<int, int> freq_;

};

Python3

# Author: Huahua

class FindSumPairs:

def __init__(self, nums1: List[int], nums2: List[int]):

self.nums1 = nums1

self.nums2 = nums2

self.freq = Counter(nums2)

def add(self, index: int, val: int) -> None:

self.freq.subtract((self.nums2[index],))

self.nums2[index] += val

self.freq.update((self.nums2[index],))

def count(self, tot: int) -> int:

return sum(self.freq[tot - a] for a in self.nums1)

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

By zxi on August 4, 2021

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

Constraints:

1 <= s.length <= 1000
s[i] is either '0' or '1'.

Solution: Greedy

Two passes, make the string starts with ‘0’ or ‘1’, count how many 0/1 swaps needed. 0/1 swaps must equal otherwise it’s impossible to swap.

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(string s) {

auto count = [&](int m) {

vector<int> swaps(2);

for (int i = 0; i < s.length(); ++i, m ^= 1)

if (s[i] - '0' != m)

++swaps[s[i] - '0'];

return swaps[0] == swaps[1] ? swaps[0] : INT_MAX;

};

int ans = min(count(0), count(1));

return ans != INT_MAX ? ans : -1;

}

};

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

By zxi on August 4, 2021

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 20

Solution 1: Brute Force

Use an array A to store all the xor subsets, for a given number x
A = A + [x ^ a for a in A]

Time complexity: O(2ⁿ)
Space complexity: O(2ⁿ)

Python3

# Author: Huahua

class Solution:

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

xors = [0]

for x in nums:

xors += [xor ^ x for xor in xors]

return sum(xors)

花花酱 LeetCode 1860. Incremental Memory Leak

By zxi on June 1, 2021

You are given two integers memory1 and memory2 representing the available memory in bits on two memory sticks. There is currently a faulty program running that consumes an increasing amount of memory every second.

At the i^th second (starting from 1), i bits of memory are allocated to the stick with more available memory (or from the first memory stick if both have the same available memory). If neither stick has at least i bits of available memory, the program crashes.

Return an array containing [crashTime, memory1_crash, memory2_crash], where crashTime is the time (in seconds) when the program crashed and memory1_crash and memory2_crash are the available bits of memory in the first and second sticks respectively.

Example 1:

Input: memory1 = 2, memory2 = 2
Output: [3,1,0]
Explanation: The memory is allocated as follows:
- At the 1^st second, 1 bit of memory is allocated to stick 1. The first stick now has 1 bit of available memory.
- At the 2^nd second, 2 bits of memory are allocated to stick 2. The second stick now has 0 bits of available memory.
- At the 3^rd second, the program crashes. The sticks have 1 and 0 bits available respectively.

Example 2:

Input: memory1 = 8, memory2 = 11
Output: [6,0,4]
Explanation: The memory is allocated as follows:
- At the 1^st second, 1 bit of memory is allocated to stick 2. The second stick now has 10 bit of available memory.
- At the 2^nd second, 2 bits of memory are allocated to stick 2. The second stick now has 8 bits of available memory.
- At the 3^rd second, 3 bits of memory are allocated to stick 1. The first stick now has 5 bits of available memory.
- At the 4^th second, 4 bits of memory are allocated to stick 2. The second stick now has 4 bits of available memory.
- At the 5^th second, 5 bits of memory are allocated to stick 1. The first stick now has 0 bits of available memory.
- At the 6^th second, the program crashes. The sticks have 0 and 4 bits available respectively.

Constraints:

0 <= memory1, memory2 <= 2³¹ - 1

Solution: Simulation

Time complexity: O(max(memory1, memory2)^0.5)
Space complexity: O(1)

Python3

class Solution:

def memLeak(self, memory1: int, memory2: int) -> List[int]:

for i in range(1, 2**30):

if max(memory1, memory2) < i:

return [i, memory1, memory2]

elif memory1 >= memory2:

memory1 -= i

else:

memory2 -= i

return None

Huahua's Tech Road

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

Solution: DP

C++

Python3

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

Solution: HashTable

C++

Python3

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

Solution: Greedy

C++

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

Solution 1: Brute Force

Python3

花花酱 LeetCode 1860. Incremental Memory Leak

Solution: Simulation

Python3