A. Number of Valid Clock Times (opens new window)

Check every possible time.

DETAILS

def countTime(self, time: str) -> int:
        def valid(t, time):
            for i in range(5):
                if time[i] != "?" and t[i] != time[i]:
                    return False
            return True
        ans = 0
        for hh in range(24):
            for mm in range(60):
                t = str(hh).zfill(2) + ":" + str(mm).zfill(2)
                ans += int(valid(t, time))
        return ans

B. Range Product Queries of Powers (opens new window)

Brute force is fine, can be improved using prefix product.

DETAILS

def productQueries(self, n: int, Q: List[List[int]]) -> List[int]:
        ans, mod = [], 10 ** 9 + 7
        n = bin(n)[2:]
        n = n[::-1]
        base = [i for i, a in enumerate(n) if a == "1"]

        for l, r in Q:
            res = 1
            for i in range(l, r + 1):
                res *= (1 << base[i])
                res %= mod
            ans.append(res)
        return ans

C. Minimize Maximum of Array

The value can only be passed forward, thus the average value is monotonically increasing.

DETAILS

def minimizeArrayValue(self, A: List[int]) -> int:
        ans = cur = A[0]
        for i in range(1, len(A)):
            cur += A[i]
            ans = max(ans, math.ceil(cur / (i + 1)))
        return ans

D. Create Components With Same Value (opens new window)

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

BFS + Topological Sort

DETAILS

def componentValue(self, A: List[int], E: List[List[int]]) -> int:
        ma, ss, n = max(A), sum(A), len(A)
        if n == 1: return 0
        G = collections.defaultdict(set)
        degree = [0] * n
        for a, b in E:
            degree[a] += 1
            degree[b] += 1
            G[a].add(b)
            G[b].add(a)
            
        def bfs(target):
            V, deg = A[:], degree[:]
            dq = collections.deque([i for i, d in enumerate(degree) if d == 1])
            
            while dq:
                ci = dq.popleft()
                if deg[ci] == 0: continue
                deg[ci] = 0
                if V[ci] == target:
                    for nxt in G[ci]:
                        deg[nxt] -= 1
                        if deg[nxt] == 0:
                            return V[nxt] == target
                        elif deg[nxt] == 1:
                            dq.append(nxt)
                else:
                    for nxt in G[ci]:
                        if deg[nxt] > 0:
                            deg[nxt] -= 1
                            V[nxt] += V[ci]
                            if deg[nxt] == 0:
                                return V[nxt] == target
                            elif deg[nxt] == 1:
                                dq.append(nxt)     
           
        for cand in range(1, ss):
            if ss % cand == 0 and bfs(cand):
                return ss // cand - 1
        return 0