304 North Cardinal St.
Dorchester Center, MA 02124

# Biweekly Contest 74 LeetCode Solution

## Problem 1 – Divide Array Into Equal Pairs Leetcode Solution

You are given an integer array `nums` consisting of `2 * n` integers.

You need to divide `nums` into `n` pairs such that:

• Each element belongs to exactly one pair.
• The elements present in a pair are equal.

Return `true` if nums can be divided into `n` pairs, otherwise return `false`.

Example 1:

``````Input: nums = [3,2,3,2,2,2]
Output: true
Explanation:
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.
``````

Example 2:

``````Input: nums = [1,2,3,4]
Output: false
Explanation:
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.
``````

Constraints:

• `nums.length == 2 * n`
• `1 <= n <= 500`
• `1 <= nums[i] <= 500`

### Divide Array Into Equal Pairs Leetcode Solution in Java

Method 1: Count and check parity

``````    public boolean divideArray(int[] nums) {
int[] cnt = new int;
for (int n : nums)
++cnt[n];
return IntStream.of(cnt).allMatch(n -> n % 2 == 0);
}
``````

Method 2: check parity by boolean array

``````    public boolean divideArray(int[] nums) {
boolean[] odd = new boolean;
for (int n : nums)
odd[n] = !odd[n];
return Arrays.equals(odd, new boolean);
}
``````

Method 3: HashSet

``````    public boolean divideArray(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
seen.remove(num);
}
}
return seen.isEmpty();
}
``````

### Divide Array Into Equal Pairs Leetcode Solution in Python3

Method 1: Count and check parity

``````    def divideArray(self, nums: List[int]) -> bool:
return all(v % 2 == 0 for v in Counter(nums).values())
``````

Method 2: check parity by boolean array

``````    def divideArray(self, nums: List[int]) -> bool:
odd = [False] * 501
for n in nums:
odd[n] = not odd[n]
return not any(odd)
``````

Method 3: HashSet

``````    def divideArray(self, nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
else:
return not seen
``````

### Divide Array Into Equal Pairs Leetcode Solution in C++

``````class Solution {
public:
bool divideArray(vector<int>& nums)
{
int n =nums.size();
sort(nums.begin(), nums.end());
int i=1;
while(i<n)
{
if(nums[i-1] != nums[i])
return false;
i = i+2;
}
return true;

}
};
``````

### Divide Array Into Equal Pairs Leetcode Solution in Python

``````class Solution:

def divideArray(self, nums: List[int]) -> bool:
lena = len(nums)
count = sum(num//2 for num in Counter(nums).values())
return (lena/2 == count)

``````

### Divide Array Into Equal Pairs Leetcode Solution in JavaScript

``````var divideArray = function(nums) {
const numMap = new Map();
for (const num of nums) {
numMap.has(num) ? numMap.delete(num) : numMap.set(num, true);
}
return numMap.size === 0;
};
``````

## Problem 2 – Maximize Number of Subsequences in a String Leetcode Solution

You are given a 0-indexed string `text` and another 0-indexed string `pattern` of length `2`, both of which consist of only lowercase English letters.

You can add either `pattern` or `pattern` anywhere in `text` exactly once. Note that the character can be added even at the beginning or at the end of `text`.

Return the maximum number of times `pattern` can occur as a subsequence of the modified `text`.

subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Example 1:

``````Input: text = "abdcdbc", pattern = "ac"
Output: 4
Explanation:
If we add pattern = 'a' in between text and text, we get "abadcdbc". Now, the number of times "ac" occurs as a subsequence is 4.
Some other strings which have 4 subsequences "ac" after adding a character to text are "aabdcdbc" and "abdacdbc".
However, strings such as "abdcadbc", "abdccdbc", and "abdcdbcc", although obtainable, have only 3 subsequences "ac" and are thus suboptimal.
It can be shown that it is not possible to get more than 4 subsequences "ac" by adding only one character.
``````

Example 2:

``````Input: text = "aabb", pattern = "ab"
Output: 6
Explanation:
Some of the strings which can be obtained from text and have 6 subsequences "ab" are "aaabb", "aaabb", and "aabbb".
``````

Constraints:

• `1 <= text.length <= 105`
• `pattern.length == 2`
• `text` and `pattern` consist only of lowercase English letters.

### Maximize Number of Subsequences in a String Leetcode Solution in Java

``````    public long maximumSubsequenceCount(String s, String pattern) {
long res = 0, cnt1 = 0, cnt2 = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == pattern.charAt(1)) {
res += cnt1;
cnt2++;
}
if (s.charAt(i) == pattern.charAt(0)) {
cnt1++;
}
}
return res + Math.max(cnt1, cnt2);
}
``````

### Maximize Number of Subsequences in a String Leetcode Solution in C++

``````    long long maximumSubsequenceCount(string text, string pattern) {
long long res = 0, cnt1 = 0, cnt2 = 0;
for (char& c: text) {
if (c == pattern)
res += cnt1, cnt2++;
if (c == pattern)
cnt1++;
}
return res + max(cnt1, cnt2);
}
``````

### Maximize Number of Subsequences in a String Leetcode Solution in Python

``````    def maximumSubsequenceCount(self, text, pattern):
res = cnt1 = cnt2 = 0
for c in text:
if c == pattern:
res += cnt1
cnt2 += 1
if c == pattern:
cnt1 += 1
return res + max(cnt1, cnt2)
``````

## Problem 3 – Minimum Operations to Halve Array Sum Leetcode Solution

You are given an array `nums` of positive integers. In one operation, you can choose any number from `nums` and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of `nums` by at least half.

Example 1:

``````Input: nums = [5,19,8,1]
Output: 3
Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.
The following is one of the ways to reduce the sum by at least half:
Pick the number 19 and reduce it to 9.5.
Pick the number 9.5 and reduce it to 4.75.
Pick the number 8 and reduce it to 4.
The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75.
The sum of nums has been reduced by 33 - 14.75 = 18.25, which is at least half of the initial sum, 18.25 >= 33/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.
``````

Example 2:

``````Input: nums = [3,8,20]
Output: 3
Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31.
The following is one of the ways to reduce the sum by at least half:
Pick the number 20 and reduce it to 10.
Pick the number 10 and reduce it to 5.
Pick the number 3 and reduce it to 1.5.
The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5.
The sum of nums has been reduced by 31 - 14.5 = 16.5, which is at least half of the initial sum, 16.5 >= 31/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.
``````

Constraints:

• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 107`

### Minimum Operations to Halve Array Sum Leetcode Solution in Java

``````    public int halveArray(int[] nums) {
PriorityQueue<Double> pq = new PriorityQueue<>(Comparator.reverseOrder());
double half = IntStream.of(nums).mapToLong(i -> i).sum() / 2d;
for (int n : nums) {
pq.offer((double)n);
}
int ops = 0;
while (half > 0) {
double d = pq.poll();
d /= 2;
half -= d;
pq.offer(d);
++ops;
}
return ops;
}
``````

### Minimum Operations to Halve Array Sum Leetcode Solution in Python3

``````    def halveArray(self, nums: List[int]) -> int:
half, ops = sum(nums) / 2, 0
heap = [-num for num in nums]
heapify(heap)
while half > 0:
num = -heappop(heap)
num /= 2.0
half -= num
heappush(heap, -num)
ops += 1
return ops
``````

### Minimum Operations to Halve Array Sum Leetcode Solution in C++

``````int halveArray(vector<int>& nums) {
double sum = accumulate(begin(nums), end(nums), 0.0), orig = sum, cnt = 0;
priority_queue<double> pq(begin(nums), end(nums));
for (; sum * 2 > orig; ++cnt) {
double n = pq.top(); pq.pop();
sum -= n / 2;
pq.push(n / 2);
}
return cnt;
}
``````

### Minimum Operations to Halve Array Sum Leetcode Solution in Python

``````class Solution:
def halveArray(self, nums: List[int]) -> int:
# Creating empty heap
maxHeap = []
heapify(maxHeap) # Creates minHeap

totalSum = 0
for i in nums:
# Adding items to the heap using heappush
# for maxHeap, function by multiplying them with -1
heappush(maxHeap, -1*i)
totalSum += i

requiredSum = totalSum / 2
minOps = 0

while totalSum > requiredSum:
x = -1*heappop(maxHeap) # Got negative value make it positive
x /= 2
totalSum -= x
heappush(maxHeap, -1*x)
minOps += 1

return minOps
``````

## Problem 4 – Minimum White Tiles After Covering With Carpets Leetcode Solution

You are given a 0-indexed binary string `floor`, which represents the colors of tiles on a floor:

• `floor[i] = '0'` denotes that the `ith` tile of the floor is colored black.
• On the other hand, `floor[i] = '1'` denotes that the `ith` tile of the floor is colored white.

You are also given `numCarpets` and `carpetLen`. You have `numCarpets` black carpets, each of length `carpetLen` tiles. Cover the tiles with the given carpets such that the number of white tiles still visible is minimum. Carpets may overlap one another.

Return the minimum number of white tiles still visible.

Example 1:

``````Input: floor = "10110101", numCarpets = 2, carpetLen = 2
Output: 2
Explanation:
The figure above shows one way of covering the tiles with the carpets such that only 2 white tiles are visible.
No other way of covering the tiles with the carpets can leave less than 2 white tiles visible.
``````

Example 2:

``````Input: floor = "11111", numCarpets = 2, carpetLen = 3
Output: 0
Explanation:
The figure above shows one way of covering the tiles with the carpets such that no white tiles are visible.
Note that the carpets are able to overlap one another.
``````

Constraints:

• `1 <= carpetLen <= floor.length <= 1000`
• `floor[i]` is either `'0'` or `'1'`.
• `1 <= numCarpets <= 1000`

### Minimum White Tiles After Covering With Carpets Leetcode Solution in Java

``````    public int minimumWhiteTiles(String s, int nc, int l) {
int n = s.length(), dp[][] = new int[n + 1][nc + 1];
for (int i = 1; i <= n; ++i) {
for (int k = 0; k <= nc; ++k) {
int jump = dp[i - 1][k] + s.charAt(i - 1) - '0';
int cover = k > 0 ? dp[Math.max(i - l, 0)][k - 1] : 1000;
dp[i][k] = Math.min(cover, jump);
}
}
return dp[n][nc];
}
``````

### Minimum White Tiles After Covering With Carpets Leetcode Solution in C++

``````    int minimumWhiteTiles(string s, int nc, int l) {
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(nc + 1));
for (int i = 1; i <= n; ++i) {
for (int k = 0; k <= nc; ++k) {
int jump = dp[i - 1][k] + s[i - 1] - '0';
int cover = k > 0 ? dp[max(i - l, 0)][k - 1] : 1000;
dp[i][k] = min(cover, jump);
}
}
return dp[n][nc];
}
``````

### Minimum White Tiles After Covering With Carpets Leetcode Solution in Python3

``````    def minimumWhiteTiles(self, A, k, l):

@lru_cache(None)
def dp(i, k):
if i <= 0: return 0
return min(int(A[i - 1]) + dp(i - 1, k), dp(i - l, k - 1) if k else 1000)

return dp(len(A), k)
``````

### Minimum White Tiles After Covering With Carpets Leetcode Solution in Python

``````class Solution:
def minimumWhiteTiles(self, floor, k, L):
@lru_cache(None)
def dp(i, t):
if t < 0: return float("inf")
if i < 0: return 0
return min(dp(i - L, t - 1), dp(i - 1, t) + int(floor[i] == "1"))

return dp(len(floor) - 1, k)
``````
##### Biweekly Contest 74 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 74 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Biweekly Contest 74 LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Biweekly Contest 74 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions