# 2021 LC Weekly Contest 222

Created: 2021/01/04 Updated:### Table of Contents

- Q2 1711 - Count Good Meals
- Q3 1712 - Ways to Split Array Into Three Subarrays
- Q4 1713 - Minimum Operations to Make a Subsequence

## Q2 1711 - Count Good Meals

### Solution: HashMap

This problem is similar to two sum question Two Sum - LeetCode What we need to do is to store and count the seen values in a HashMap/Dict, then once we found the target (power of 2 minus current value) is in the map, we can increment it to our sum result.

- since the deliciousness is within a fixed range which is 2^20 then we can iterate each power of 2 for given deliciousness value.
- use bitwise operation for power of 2, 2 « x

- Time: O(21*n) where n is length of deliciousness and 21 is the power iteration count from 1.
- Space: O(n) where n is length of deliciousness.

```
from collections import Counter
class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
# similar to two sum.
res = 0
counted = Counter()
for d in deliciousness:
for i in range(22):
twoPorwer = 1 << i
res += counted[twoPorwer - d]
counted[d] += 1
return res % (10**9 + 7)
```

## Q3 1712 - Ways to Split Array Into Three Subarrays

### Solution: PrefixSum + Binary Search

- TODO(Write binary search to find leftmost or rightmost by hand)

### Solution: PrefixSum + Two pointer

PrefixSum takes O(n) but save our time for compute any sum of sublist by O(1).
We use **i, j, k** to be the variables for computing.

**i**: first pointer we choose.**j**: leftmost pointer that we can choose for second pointer, inclusive.**k**: k - 1 is rightmost pointer that we can choose for second pointer, exclusive.

For finding j: prefixSum[i] * 2 == prefixSum[j] -> j+1

For finding k: prefixSum[-1] - prefixSum[i] >= (prefixSum[k] - prefixSum[i]) * 2 -> k+1

- Time: O(n) since j and k never decreases.
- Space: O(n) where n is length of nums, for saving prefixSum. can be O(1) if replacing input into prefixSum.

```
class Solution:
def waysToSplit(self, nums: List[int]) -> int:
mod = 10**9 + 7
# prefix sum O(n)
prefixSum = []
curSum = 0
for num in nums:
curSum += num
prefixSum.append(curSum)
# i, j ,k
# right pointer can be chosed from j ~ k
# leftmost j: prefix[i] * 2 == prefix[j]
# rightmost k: (prefix[-1] - prefix[i]) // 2 == prefix[k] - prefix[i]
res = j = k = 0
for i in range(len(nums)):
# Find qualified [j, k)
# j might be greater than i+1 after first for.
# j is inclusive
j = max(i + 1, j)
while j < len(nums)-1 and prefixSum[i] * 2 > prefixSum[j]:
j += 1
# k is exclusive
k = max(j, k)
while k < len(nums)-1 and prefixSum[-1] - prefixSum[i] >= (prefixSum[k] - prefixSum[i]) * 2:
k += 1
res += (k - j)
return res % mod
```