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 < nsuch 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 <= 100
  • 1 <= 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 to finalSum): (12)(2 + 10)(2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot 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].

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.length
  • 3 <= n <= 105
  • 0 <= nums1[i], nums2[i] <= n - 1
  • nums1 and nums2 are 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

Find on LeetCode

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

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.