A. Two Furthest Houses With Different Colors (opens new window)

Brute Force.

DETAILS

def maxDistance(self, A: List[int]) -> int:
        n, ans = len(A), 1
        for i in range(n - 1):
            for j in range(i + 1, n):
                if A[i] != A[j]:
                    ans = max(ans, j - i)
        return ans

B. Watering Plants (opens new window)

Simulate.

DETAILS

def wateringPlants(self, A: List[int], cap: int) -> int:
        n, res, idx, s, cur = len(A), [], 0, 0, cap
        while idx < n:
            if cur >= A[idx]:
                cur -= A[idx]
                s += 1
            else:
                res.append(s)
                s = 1
                cur = cap - A[idx]
            idx += 1
        if s != 0:
            res.append(s)

        ans, pre = 0, 0
        for x in res:
            pre += x
            ans += 2 * pre
        ans -= pre
        return ans

C. Range Frequency Queries (opens new window)

Binary Search

DETAILS

class RangeFreqQuery:
    def __init__(self, arr: List[int]):
        self.dict = collections.defaultdict(list)
        for i, x in enumerate(arr):
            self.dict[x].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if not self.dict[value]:
            return 0
        lft = bisect.bisect_left(self.dict[value], left)
        rgt = bisect.bisect_right(self.dict[value], right)
        return rgt - lft

D. Sum of k-Mirror Numbers (opens new window)

Brute-Force

DETAILS

def kMirror(self, k: int, n: int) -> int:
        res = collections.defaultdict(list)
        res[2] = [1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939]
        res[3] = [1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138]
        res[4] = [1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715]
        res[5] = [1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121]
        res[6] = [1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654]
        res[7] = [1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446]
        res[8] = [1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355]
        res[9] = [1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442]
        def helper(num, base):
            if num < base:
                return [num]
            quotient = num // base
            remainder = num % base
            conver_stack = [remainder]
            while quotient >= base:
                remainder = quotient % base
                quotient = quotient // base
                conver_stack.append(remainder)
            conver_stack.append(quotient)
            return conver_stack

        return sum(res[k][:n])