Physical Address
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 * n1 <= n <= 5001 <= 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[501];
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[501];
for (int n : nums)
odd[n] = !odd[n];
return Arrays.equals(odd, new boolean[501]);
}
Method 3: HashSet
public boolean divideArray(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (!seen.add(num)) {
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:
seen.discard(num)
else:
seen.add(num)
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[0] or pattern[1] 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.
A 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[0] = 'a' in between text[1] and text[2], 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 <= 105pattern.length == 2textandpatternconsist 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[1])
res += cnt1, cnt2++;
if (c == pattern[0])
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[1]:
res += cnt1
cnt2 += 1
if c == pattern[0]:
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 <= 1051 <= 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 theithtile of the floor is colored black.- On the other hand,
floor[i] = '1'denotes that theithtile 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 <= 1000floor[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
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 >>
