304 North Cardinal St.
Dorchester Center, MA 02124

# 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 `s`excluding 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]].push_back(edges[i]);
m[edges[i]].push_back(edges[i]);
}
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 =  * 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
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++)
for(int [] edge : edges){
}

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); // 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;
visited[node] = true;
count++;
for(int curr : x.get(node))
dfs(curr, visited, count);
return count;
}
``````

### 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 = 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 = {};
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