# 2021 LC Weekly Contest 222

### Table of Contents

Contest - LeetCode 222

## 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.

1. since the deliciousness is within a fixed range which is 2^20 then we can iterate each power of 2 for given deliciousness value.
2. 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

• 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
``````

TODO