A. Minimum Bit Flips to Convert Number (opens new window)

Bitwise operation.

DETAILS

def minBitFlips(self, start: int, goal: int) -> int:
        return bin(start ^ goal).count("1")

B. Find Triangular Sum of an Array (opens new window)

DETAILS

def triangularSum(self, A: List[int]) -> int:
        while len(A) > 1:
            tmp = [x + y for x, y in zip(A[:-1], A[1:])]
            A = tmp
        return A[0] % 10

DETAILS

C. Number of Ways to Select Buildings (opens new window)

Left and right DP. Initialize two arrays lft and rgt. lft[i] stores the number of buildings of different type on s[i]'s left. Same for rgt. Then iterate over lft and rgt to calculate number of valid ways.

DETAILS

def numberOfWays(self, s: str) -> int:
        n = len(s)
        lft, rgt = [0] * n, [0] * n
        
        counter = collections.defaultdict(int)
        for i, ch in enumerate(s):
            lft[i] = i - counter[ch]
            counter[ch] += 1
            
        counter = collections.defaultdict(int)
        for i, ch in enumerate(s[::-1]):
            rgt[n - i - 1] = i - counter[ch]
            counter[ch] += 1
        
        ans = 0
        for i in range(n):
            if 0 not in [lft[i], rgt[i]]:
                ans += lft[i] * rgt[i]
        return ans

D. Sum of Scores of Built Strings (opens new window)

z-function

DETAILS

def sumScores(self, s: str) -> int:
        n, l, r = len(s), 0, 0
        z = [0] * n
        for i in range(1, n):
            if i <= r and z[i - l] < r - i + 1:
                z[i] = z[i - l]
            else:
                z[i] = max(0, r - i + 1)
                while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                    z[i] += 1
            if i + z[i] - 1 > r:
                l = i
                r = i + z[i] - 1
        return sum(z) + n