🏰 Palace Window

Search

SearchSearch

Analytical

Problems that require the answerer to reason about some equation or compute some quantity in order to solve them but don’t really fit firmly in any other solution methods.

 

Sum of Odds & Evens Equal After Removal

Given an array of integers, choose one indices to remove that makes the even indexed elements sum to the same value as the odd index elements. Return the total number of indices that can be removed in this way.

Explore

  6 1 7 4 1
  csl -> 6,0 6,1 13,1 13,5 14,5
  csr -> 1,0 1,4 8,4  8,5  14,5
  1. Calculate the cumulative sum from the left & right of odd & even indices.
  2. For all i, compare csl[i-1]→even + csr[i+1]→odd to csl[i-1]→odd + csr[i+1]→even because removing one index from csr swaps even & odd sums.
  3. Return the number of comparisons that return true.

Python Solution

class Solution:
    def waysToMakeFair(self, a) -> int:
        csl, csr, soln, N = [[a[0], 0]], [], 0, len(a)
        if N == 0:
            return 0
        if N == 1:
            return 1
 
        for i in range(1, N):
            if i % 2 == 0:
                csl += [[csl[i - 1][0] + a[i], csl[i - 1][1]]]
            else:
                csl += [[csl[i - 1][0], csl[i - 1][1] + a[i]]]
 
        if (N - 1) % 2 == 0:
            csr += [[a[N - 1], 0]]
        else:
            csr += [[0, a[N - 1]]]
 
        # TODO: make CSR go the same direction as the input array to simplify
        for i in range(1, N):
            j = N - 1 - i
            if j % 2 == 0:
                csr += [[csr[i - 1][0] + a[j], csr[i - 1][1]]]
            else:
                csr += [[csr[i - 1][0], csr[i - 1][1] + a[j]]]
 
        if csr[N - 2][0] == csr[N - 2][1]:
            soln += 1
        if csl[N - 2][0] == csl[N - 2][1]:
            soln += 1
 
        for i in range(1, N - 1):
            j = N - 1 - i
            if csl[i - 1][0] + csr[j - 1][1] == csl[i - 1][1] + csr[j - 1][0]:
                soln += 1
 
        return soln

Complexity

We calculate the cumulative sums from the left & the right using O(n) space & then iterate them to find which indices can be removed in O(n) total time.

 

Left & Right Sum Differences

Given an array of integers, find the difference in the absolute value of the cumulative sum from the left & the right at each index. The value at the current index is not included in the calculations.

Python Solution

class Solution:
    def leftRigthDifference(self, a) -> List[int]:
        n = len(a)
        if n == 1:
            return [0]
 
        csl, csr, soln = [0] * n, [0] * n, [0] * n
 
        csl[0] = a[0]
        csr[n - 1] = a[n - 1]
        for i in range(1, n):
            j = n - 1 - i
            csl[i] = csl[i - 1] + a[i]
            csr[j] = csr[j + 1] + a[j]
 
        soln[0] = csr[1]
        soln[n - 1] = csl[n - 2]
        for i in range(1, n - 1):
            soln[i] = abs(csl[i - 1] - csr[i + 1])
 
        return soln

Graph View