Biweekly Contest 81 Leetcode Solution

Problem 1 – Count Asterisks Leetcode Solution

You are given a string s, where every two consecutive vertical bars '|' are grouped into a pair. In other words, the 1st and 2nd '|' make a pair, the 3rd and 4th '|' make a pair, and so forth.

Return the number of '*' in sexcluding the '*' between each pair of '|'.

Note that each '|' will belong to exactly one pair.

Example 1:

Input: s = "l|*e*et|c**o|*de|"
Output: 2
Explanation: The considered characters are underlined: "l|*e*et|c**o|*de|".
The characters between the first and second '|' are excluded from the answer.
Also, the characters between the third and fourth '|' are excluded from the answer.
There are 2 asterisks considered. Therefore, we return 2.

Example 2:

Input: s = "iamprogrammer"
Output: 0
Explanation: In this example, there are no asterisks in s. Therefore, we return 0.

Example 3:

Input: s = "yo|uar|e**|b|e***au|tifu|l"
Output: 5
Explanation: The considered characters are underlined: "yo|uar|e**|b|e***au|tifu|l". There are 5 asterisks considered. Therefore, we return 5

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters, vertical bars '|', and asterisks '*'.
  • s contains an even number of vertical bars '|'.

Count Asterisks LeetCode Solution in C++

   int countAsterisks(string s) {
        int res = 0, sign = 1;
        for (char& c : s)
            if ((sign ^= c == '|') && c == '*')
                res++;
        return res;
    }

Count Asterisks LeetCode Solution in Java

public int countAsterisks(String s) {
        int res = 0, bars = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '*' && bars % 2 == 0)
                res++;
            if (s.charAt(i) == '|')
                bars++;
        }
        return res;
    }
    
    return max;
};

Count Asterisks LeetCode Solution in Python

def countAsterisks(self, s: str) -> int:
        return sum([a.count('*') for a in s.split('|')][0::2])

Problem 2 – Count Unreachable Pairs of Nodes in an Undirected Graph LeetCode Solution

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1:

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Example 2:

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].
Therefore, we return 14.

Constraints:

  • 1 <= n <= 105
  • 0 <= edges.length <= 2 * 105
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • There are no repeated edges.

Count Unreachable Pairs of Nodes in an Undirected Graph LeetCode Solution in C++

class Solution {
public:
    typedef long long ll;
    void dfs(int node, unordered_map<int,vector<int>>& m, ll& cnt, vector<int>& vis){
        vis[node] = 1;
        cnt++;
        for(auto& i: m[node]){
            if(vis[i]==0) dfs(i,m,cnt,vis);   
        }
    }
    long long countPairs(int n, vector<vector<int>>& edges) {
        unordered_map<int,vector<int>> m; // making adjacency list
        for(int i=0;i<edges.size();i++){
            m[edges[i][0]].push_back(edges[i][1]);
            m[edges[i][1]].push_back(edges[i][0]);
        }
        ll ans = ((ll)n*(n-1))/2;
        vector<int> vis(n,0);
        for(int i=0;i<n;i++){
            if(vis[i]==0){ // as node is not visited, we find the no. of nodes in current component.
                ll cnt = 0;
                dfs(i,m,cnt,vis);
                ans -= (cnt*(cnt-1))/2;
            }
        }
        return ans;
    }
};

Count Unreachable Pairs of Nodes in an Undirected Graph LeetCode Solution in Python

class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.rank = [1] * size
    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1
                
class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        dsu = UnionFind(n)
        for u, v in edges:
            dsu.union(u, v) 
        C = Counter([dsu.find(i) for i in range(n)])
        groupCounts = list(C.values())
        ans = 0
        firstGroupCount = groupCounts[0]
        for i in range(1, len(groupCounts)):
            ans += firstGroupCount * groupCounts[i]
            firstGroupCount += groupCounts[i]  
        return ans

Count Unreachable Pairs of Nodes in an Undirected Graph LeetCode Solution in Java

List<List<Integer>> x = new ArrayList<>();
public long countPairs(int n, int[][] edges) {
    for(int i=0; i<n; i++)
        x.add(new ArrayList<>());
    for(int [] edge : edges){
        x.get(edge[0]).add(edge[1]);  // make graph
        x.get(edge[1]).add(edge[0]);
    }

    long res = 0, sum = n;
    boolean[] visited = new boolean[n];
    for(int i=0; i<n; i++)
        if(!visited[i]){
            int curr = dfs(i, visited, new int[1]); // find size of connected component
            sum = sum-curr;
            res += curr*sum;
        }
    return res;
}

int dfs(int node, boolean[] visited, int[] count){ 
    if(visited[node]) return count[0];
    visited[node] = true;
    count[0]++;
    for(int curr : x.get(node))
        dfs(curr, visited, count);
    return count[0];
}

Problem 3 – Maximum XOR After Operations LeetCode Solution

You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).

Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.

Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.

Example 1:

Input: nums = [3,2,4,6]
Output: 7
Explanation: Apply the operation with x = 4 and i = 3, num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2.
Now, nums = [3, 2, 4, 2] and the bitwise XOR of all the elements = 3 XOR 2 XOR 4 XOR 2 = 7.
It can be shown that 7 is the maximum possible bitwise XOR.
Note that other operations may be used to achieve a bitwise XOR of 7.

Example 2:

Input: nums = [1,2,3,9,2]
Output: 11
Explanation: Apply the operation zero times.
The bitwise XOR of all the elements = 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11.
It can be shown that 11 is the maximum possible bitwise XOR.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 108

Maximum XOR After Operations LeetCode Solution in Java

    public int maximumXOR(int[] nums) {
        int res = 0;
        for (int a: nums)
            res |= a;
        return res;
    }

Maximum XOR After Operations LeetCode Solution in C++

    int maximumXOR(vector<int>& nums) {
        int res = 0;
        for (int a : nums)
            res |= a;
        return res;
    }

Maximum XOR After Operations LeetCode Solution in Python

    def maximumXOR(self, nums):
        return reduce(ior, nums)

Problem 4 – Number of Distinct Roll Sequences LeetCode Solution

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

  1. The greatest common divisor of any adjacent values in the sequence is equal to 1.
  2. There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the ith roll is equal to the value of the jth roll, then abs(i - j) > 2.

Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 109 + 7.

Two sequences are considered distinct if at least one element is different.

Example 1:

Input: n = 4
Output: 184
Explanation: Some of the possible sequences are (1, 2, 3, 4), (6, 1, 2, 3), (1, 2, 3, 1), etc.
Some invalid sequences are (1, 2, 1, 3), (1, 2, 3, 6).
(1, 2, 1, 3) is invalid since the first and third roll have an equal value and abs(1 - 3) = 2 (i and j are 1-indexed).
(1, 2, 3, 6) is invalid since the greatest common divisor of 3 and 6 = 3.
There are a total of 184 distinct sequences possible, so we return 184.

Example 2:

Input: n = 2
Output: 22
Explanation: Some of the possible sequences are (1, 2), (2, 1), (3, 2).
Some invalid sequences are (3, 6), (2, 4) since the greatest common divisor is not equal to 1.
There are a total of 22 distinct sequences possible, so we return 22.

Constraints:

  • 1 <= n <= 104

Number of Distinct Roll Sequences LeetCode Solution in C++

int dp[10001][7][7] = {};
int distinctSequences(int n, int p = 0, int pp = 0) {
    if (n == 0)
        return 1;
    if (dp[n][p][pp] == 0)
        for (int d = 1; d < 7; ++d)
            if (d != p && d != pp && (p == 0 || gcd(d, p) == 1))
                dp[n][p][pp] = (dp[n][p][pp] + distinctSequences(n - 1, d, p)) % 1000000007;
    return dp[n][p][pp];
}

Number of Distinct Roll Sequences LeetCode Solution in Python

    def distinctSequences(self, n: int) -> int:
        mod = 10**9 + 7
        dp, dp2 = {(7, 7): 1}, Counter()
        for _ in range(n):
            for i, j in dp:
                for k in range(1, 7):
                    if k != i and k != j and gcd(j, k) == 1:
                        dp2[j, k] = (dp2[j, k] + dp[i, j]) % mod
            dp, dp2 = dp2, Counter()
        return sum(dp.values()) % mod

Number of Distinct Roll Sequences LeetCode Solution in Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private static final int k = 6, p = 1_000_000_007;

    public int distinctSequences(int n) {
        if (n == 1) return 6;
        int counter = 0;
        Map<Pair, Integer> map = new HashMap<>();
		//enumerate possible pairs
        for (int i = 1; i < k; i++) {
            for (int j = i + 1; j <= k; j++) {
                if ((i % 2 != 0 || j % 2 != 0) && (i % 3 != 0 || j % 3 != 0)) {
                    map.put(new Pair(i, j), counter++);
                    map.put(new Pair(j, i), counter++);
                }
            }
        }

        if (n == 2) return counter;

        long[][] matrix = new long[counter][counter];
		//for every possible pairs (a,b) check if (a,b,c) is possible
		// if so set A[index of (b,c)][index of (a,b)] = 1
        for (Map.Entry<Pair, Integer> entry : map.entrySet()) {
            int a = entry.getKey().x, b = entry.getKey().y;
            for (int c = 1; c <= k; c++) {
                if (a == c || b == c || b % 2 == 0 && c % 2 == 0 || b % 3 == 0 && c % 3 == 0) continue;
                matrix[map.get(new Pair(b, c))][entry.getValue()] = 1;
            }
        }

        long[][] power = matrixPower(matrix, n - 2);
        int ans = 0;
        for (long[] row : power) {
            for (long a : row) {
                ans += a;
                if (ans >= p) ans -= p;
            }
        }
        return ans;
    }

    private record Pair(int x, int y) {
    }


    private static long[][] matrixPower(long[][] base, long pow) {
        int n = base.length;
        long[][] res = new long[n][n];
        for (int i = 0; i < n; i++) {
            res[i][i] = 1;
        }
        while (pow != 0) {
            if ((pow & 1) != 0) {
                res = multiplyMatrix(res, base);
                --pow;
            } else {
                base = multiplyMatrix(base, base);
                pow >>= 1;
            }
        }
        return res;
    }

    private static long[][] multiplyMatrix(long[][] a, long[][] b) {
        int n = a.length;
        long[][] ans = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                    if (ans[i][j] >= p) ans[i][j] %= p; // remove if not modular
                }
            }
        }
        return ans;
    }
}

Biweekly Contest 81 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 81 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 81 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Biweekly Contest 81 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.