A. Count Asterisks (opens new window)

Only count the *'s before the even number of |.

DETAILS

def countAsterisks(self, s: str) -> int:
        cnt, ans = True, 0
        for ch in s:
            if ch == '*': ans += int(cnt)
            if ch == '|': cnt ^= True
        return ans

B. Count Unreachable Pairs of Nodes in an Undirected Graph (opens new window)

DSU, sort nodes into connected groups. If the total number of nodes is N, for a group of a, the number of unreachable pairs to this group is (N-a)*a, thus we just need to find all such groups. Notice that we count pairs two times, divide the answer by 2.

DETAILS

class DSU:
    def __init__(self, n):
        self.root = list(range(n))
        self.rk = [1] * n
    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.rk[rx] > self.rk[ry]:
                rx, ry = ry, rx
            self.root[rx] = ry
            self.rk[ry] += self.rk[rx]

class Solution:
    def countPairs(self, n: int, A: List[List[int]]) -> int:
        dsu = DSU(n)
        for a, b in A:
            dsu.union(a, b)
        ans = 0
        gp = {}
        for i in range(n):
            rt = dsu.find(i)
            if rt not in gp:
                gp[rt] = dsu.rk[rt]
        for key, val in gp.items():
            ans += val * (n - val)
        return ans // 2

C. Maximum XOR After Operations (opens new window)

DETAILS

def maximumXOR(self, nums: List[int]) -> int:
        a, b = 0, 0
        for num in nums:
            a |= num
            b &= num
        return a - b

D. Number of Distinct Roll Sequences (opens new window)

Please refer to This LC Discussion (opens new window) for my solutions in English.

2-d DP.

DETAILS

def distinctSequences(self, n: int) -> int:
        if n < 2: 
            return 6
        
        P = {1: {2, 3, 4, 5, 6}, 2: {1, 3, 5}, 3: {1, 2, 4, 5}, 4: {1, 3, 5}, 5: {1, 2, 3, 4, 6}, 6: {1, 5}}
        mod = 1000000007
        
        prev = [[0] * 7 for _ in range(7)]
        for i in range(1, 7):
            for j in P[i]:
                prev[i][j] = 1

        for _ in range(n - 2):
            curr = [[0] * 7 for _ in range(7)]
            for i in range(1, 7):
                for j in P[i]:
                    for k in range(1, 7):
                        if k != i:
                            curr[i][j] += prev[j][k]
                            curr[i][j] %= mod          
            prev = curr[:]
        return sum(sum(x) for x in prev) % mod