Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Biweekly Contest 72 LeetCode Solution
Problem 1 – Count Equal and Divisible Pairs in an Array Leetcode Solution
Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.
Example 1:
Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.
Example 2:
Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.
Constraints:
1 <= nums.length <= 1001 <= nums[i], k <= 100
Count Equal and Divisible Pairs in an Array Leetcode Solution in C++
int countPairs(vector<int>& nums, int k) {
int res = 0;
unordered_map<int, vector<int>> m;
for (int i = 0; i < nums.size(); ++i)
m[nums[i]].push_back(i);
for (auto &[n, ids] : m) {
unordered_map<int, int> gcds;
for (auto i : ids) {
auto gcd_i = gcd(i, k);
for (auto &[gcd_j, cnt] : gcds)
res += gcd_i * gcd_j % k ? 0 : cnt;
++gcds[gcd_i];
}
}
return res;
}
Count Equal and Divisible Pairs in an Array Leetcode Solution in Java
public int countPairs(int[] nums, int k) {
Map<Integer, List<Integer>> indices = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
indices.computeIfAbsent(nums[i], l -> new ArrayList<>()).add(i);
}
int cnt = 0;
for (List<Integer> ind : indices.values()) {
for (int i = 0; i < ind.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (ind.get(i) * ind.get(j) % k == 0) {
++cnt;
}
}
}
}
return cnt;
}
Count Equal and Divisible Pairs in an Array Leetcode Solution in Python 3
def countPairs(self, nums: List[int], k: int) -> int:
cnt, d = 0, defaultdict(list)
for i, n in enumerate(nums):
d[n].append(i)
for indices in d.values():
for i, a in enumerate(indices):
for b in indices[: i]:
if a * b % k == 0:
cnt += 1
return cnt
Count Equal and Divisible Pairs in an Array Leetcode Solution in Python
class Solution:
def countPairs(self, nums: List[int], k: int) -> int:
count = 0
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if(nums[i] == nums[j] and (i*j)%k==0):
count += 1
return count
Problem 2 – Find Three Consecutive Integers That Sum to a Given Number Leetcode Solution
Given an integer num, return three consecutive integers (as a sorted array) that sum to num. If num cannot be expressed as the sum of three consecutive integers, return an empty array.
Example 1:
Input: num = 33
Output: [10,11,12]
Explanation: 33 can be expressed as 10 + 11 + 12 = 33.
10, 11, 12 are 3 consecutive integers, so we return [10, 11, 12].
Example 2:
Input: num = 4
Output: []
Explanation: There is no way to express 4 as the sum of 3 consecutive integers.
Constraints:
0 <= num <= 1015
Find Three Consecutive Integers That Sum to a Given Number Leetcode Solution in C++
vector<long long> sumOfThree(long long num) {
if (num % 3 != 0) {
return {};
}
long long a = num / 3 - 1;
return {a, a + 1, a + 2};
}
Find Three Consecutive Integers That Sum to a Given Number Leetcode Solution in Java
public long[] sumOfThree(long num) {
if (num % 3 != 0) {
return new long[0];
}
long a = num / 3 - 1;
return new long[] {a, a + 1, a + 2};
}
Find Three Consecutive Integers That Sum to a Given Number Leetcode Solution in Python
def sumOfThree(self, num):
if num % 3 != 0:
return []
a = num // 3 - 1
return [a, a + 1, a + 2]
Find Three Consecutive Integers That Sum to a Given Number Leetcode Solution in Python 3
class Solution:
def sumOfThree(self, num: int) -> List[int]:
return [] if num % 3 else [num//3-1, num//3, num//3+1]
Problem 3 – Maximum Split of Positive Even Integers Leetcode Solution
You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.
- For example, given
finalSum = 12, the following splits are valid (unique positive even integers summing up tofinalSum):(12),(2 + 10),(2 + 4 + 6), and(4 + 8). Among them,(2 + 4 + 6)contains the maximum number of integers. Note thatfinalSumcannot be split into(2 + 2 + 4 + 4)as all the numbers should be unique.
Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.
Example 1:
Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6].
Note that [2,6,4], [6,2,4], etc. are also accepted.
Example 2:
Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.
Example 3:
Input: finalSum = 28
Output: [6,8,2,12]
Explanation: The following are valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24).
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.Constraints:
1 <= finalSum <= 1010
Maximum Split of Positive Even Integers Leetcode Solution in C++
class Solution {
public:
vector<long long> maximumEvenSplit(long long n) {
if(n%2) // odd
return {};
vector<long long> ans;
long long i = 2;
long long crSum=0;
while((crSum+i)<= n)
{
ans.push_back(i);
crSum+=i;
i+=2;
}
// add remaining difference to the last value in answer list
int sz = ans.size();
ans[sz-1] += (n-crSum);
return ans;
}
};
Maximum Split of Positive Even Integers Leetcode Solution in Java
public List<Long> maximumEvenSplit(long f) {
LinkedList<Long> ans = new LinkedList<>();
if (f % 2 == 0) {
long i = 2;
while (i <= f) {
ans.offer(i);
f -= i;
i += 2;
}
ans.offer(f + ans.pollLast());
}
return ans;
}
Maximum Split of Positive Even Integers Leetcode Solution in Python 3
def maximumEvenSplit(self, f: int) -> List[int]:
ans, i = [], 2
if f % 2 == 0:
while i <= f:
ans.append(i)
f -= i
i += 2
ans[-1] += f
return ans
Maximum Split of Positive Even Integers Leetcode Solution in Python
class Solution:
def maximumEvenSplit(self, finalSum: int) -> List[int]:
l=[]
if finalSum%2!=0:
return l
else:
s=0
i=2 # even pointer 2, 4, 6, 8, 10, 12...........
while(s<finalSum):
s+=i #sum
l.append(i) # append the i in list
i+=2
if s==finalSum: #if sum s is equal to finalSum then no modidfication required
return l
else:
l.pop(l.index(s-finalSum)) #Deleting the element which makes s greater than finalSum
return l
Maximum Split of Positive Even Integers Leetcode Solution in JavaScript
var maximumEvenSplit = function(finalSum) {
if(finalSum % 2) return [];
const set = new Set();
let n = 2, sum = 0;
while(sum < finalSum) {
sum += n;
set.add(n);
n += 2;
}
set.delete(sum - finalSum);
return [...set];
};
Problem 4 – Count Good Triplets in an Array Leetcode Solution
You are given two 0-indexed arrays nums1 and nums2 of length n, both of which are permutations of [0, 1, ..., n - 1].
A good triplet is a set of 3 distinct values which are present in increasing order by position both in nums1 and nums2. In other words, if we consider pos1v as the index of the value v in nums1 and pos2v as the index of the value v in nums2, then a good triplet will be a set (x, y, z) where 0 <= x, y, z <= n - 1, such that pos1x < pos1y < pos1z and pos2x < pos2y < pos2z.
Return the total number of good triplets.
Example 1:
Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output: 1
Explanation:
There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3).
Out of those triplets, only the triplet (0,1,3) satisfies pos2x < pos2y < pos2z. Hence, there is only 1 good triplet.
Example 2:
Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
Output: 4
Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).
Constraints:
n == nums1.length == nums2.length3 <= n <= 1050 <= nums1[i], nums2[i] <= n - 1nums1andnums2are permutations of[0, 1, ..., n - 1].
Count Good Triplets in an Array Leetcode Solution in Python
from sortedcontainers import SortedList
class Solution:
def goodTriplets(self, A: List[int], B: List[int]) -> int:
# Index of a (from A) in B.
pos = [0] * len(A)
for idx, b in enumerate(B):
pos[b] = idx
# Build pre_a[i]: number of elements on a[i]'s left in both A and B.
# pos_in_b: sorted indexes (in B) of all the visited elements in A.
pos_in_b, pre_a = SortedList([pos[A[0]]]), [0]
for a in A[1:]:
pos_in_b.add(pos[a])
pre_a.append(pos_in_b.bisect_left(pos[a]))
# Build suf_a[i]: number of elements on a[i]'s right in both A and B.
pos_in_b, suf_a = SortedList([pos[A[-1]]]), [0]
for a in reversed(A[:len(A)-1]):
idx = pos_in_b.bisect(pos[a])
suf_a.append(len(pos_in_b) - idx)
pos_in_b.add(pos[a])
suf_a.reverse()
# Sum up all unique triplets centered on A[i].
ans = 0
for x, y in zip(pre_a, suf_a):
ans += x * y
return ans
Count Good Triplets in an Array Leetcode Solution in C++
constexpr int static n = 100000;
int bt[n + 1] = {};
int prefix_sum(int i) {
int sum = 0;
for (i = i + 1; i > 0; i -= i & (-i))
sum += bt[i];
return sum;
}
void add(int i, int val) {
for (i = i + 1; i <= n; i += i & (-i))
bt[i] += val;
}
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
long long res = 0, sz = nums1.size();
vector<int> ids(sz);
for (int i = 0; i < sz; ++i)
ids[nums2[i]] = i;
for (int i = 0; i < sz - 1; ++i) {
int mid = ids[nums1[i]], sm = prefix_sum(mid), gr = sz - 1 - mid - (i - sm);
res += (long long)sm * gr;
add(mid, 1);
}
return res;
}
Count Good Triplets in an Array Leetcode Solution in Python 3
class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
hashmap2 = {}
for i in range(n):
hashmap2[nums2[i]] = i
indices = []
for num in nums1:
indices.append(hashmap2[num])
from sortedcontainers import SortedList
left, right = SortedList(), SortedList()
leftCount, rightCount = [], []
for i in range(n):
leftCount.append(left.bisect_left(indices[i]))
left.add(indices[i])
for i in range(n - 1, -1, -1):
rightCount.append(len(right) - right.bisect_right(indices[i]))
right.add(indices[i])
count = 0
for i in range(n):
count += leftCount[i] * rightCount[n - 1 - i]
return count
Count Good Triplets in an Array Leetcode Solution in Python
class Solution {
public long goodTriplets(int[] nums1, int[] nums2) {
int n=nums1.length;
int []pos = new int[n];
FenwickTree ft = new FenwickTree(n+1);
for(int i=0;i<n;i++)
pos[nums2[i]]=i;
long []left=new long[n];
long []right = new long[n];
for(int i=0;i<n;i++){
int idx = pos[nums1[i]];
left[i] = ft.sum(idx-1);
ft.update(idx,1);
}
ft=new FenwickTree(n+1);
for(int i=n-1;i>=0;i--){
int idx = pos[nums1[i]];
right[i]= ft.sum(n+1)-ft.sum(idx);
ft.update(idx,1);
}
long ans=0;
for (int i=0;i<n;i++)
ans+= left[i]*right[i];
return ans;
}
}
class FenwickTree {
int[] bit;
int n;
FenwickTree(int n) {
this.n = n;
this.bit = new int[n + 2];
}
public void update(int i, int val) {
i++;
while (i < bit.length) {
bit[i] += val;
i += (i & (-i));
}
}
public int sum(int i) {
int sum = 0;
i++;
while (i > 0) {
sum += bit[i];
i -= (i & (-i));
}
return sum;
}
}
Biweekly Contest 72 LeetCode Solution Review:
In our experience, we suggest you solve this Biweekly Contest 72 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 72 LeetCode Solution
Conclusion:
I hope this Biweekly Contest 72 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 >>
