Physical Address
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 5Constraints:
1 <= s.length <= 1000sconsists of lowercase English letters, vertical bars'|', and asterisks'*'.scontains 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 <= 1050 <= edges.length <= 2 * 105edges[i].length == 20 <= ai, bi < nai != 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 <= 1050 <= 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:
- The greatest common divisor of any adjacent values in the sequence is equal to
1. - There is at least a gap of
2rolls between equal valued rolls. More formally, if the value of theithroll is equal to the value of thejthroll, thenabs(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
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 >>
