Trường hợp ngoại lệ

Nếu A chỉ có một phần tử thì giá trị trả về sẽ là gì? Người đi phỏng vấn phải hỏi ngược lại được người phỏng vấn trường hợp này.

Cách giải đơn giản

Cách giải đơn giản nhất là ta thực hiện hai vòng lặp để tính giá trị của từng phần tử của danh sách B.

def solve(A):
  B = [1] * len(A)
  for i in xrange(len(A)):
    for j in xrange(len(A)):
      if i != j:
        B[i] *= A[j]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải này có độ phức tạp là O(n^2).

Cách giải O(n)

Có hai nhận xét đơn giản sau:

# Nếu như trong số phần tử còn lại có giá trị 0, thì tích số cũng sẽ là 0. # Giá trị của B[i] sẽ là tích của toàn bộ các phần tử trong A, chia cho A[i]. Ta có thể tính tích của toàn bộ các phần tử trong A qua một vòng lặp, và dùng một vòng lặp khác để tính từng giá trị của B.

def solve(A):
  nr_zeros = 0
  product = 1
  for i in xrange(len(A)):
    if A[i] == 0:
      nr_zeros += 1
    else:
      product *= A[i]
  if nr_zeros >= 2:
    return [0] * len(A)
  B = [0] * len(A)
  for i in xrange(len(B)):
    if A[i] == 0:
      B[i] = product
    elif nr_zeros != 1:
      B[i] = product / A[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Cách giải không dùng phép chia

Ta nhận thấy rằng B[i] là tích của các phần tử từ 0 đến i-1 và từ i+1 đến n của A (với n là số phần tử trong A). Nói một cách khác, giá trị trong B là tích của hai phần liên tục từ bên trái, và từ bên phải của A. Do đó, ta sẽ sử dụng hai danh sách tạm left_product và right_product để chứa tích các phần tử trong A từ bên trái, và từ bên phải, loại trừ phần tử đang xét.

def solve(A):
  left_product = [1] * len(A)
  right_product = [1] * len(A)
  for i in xrange(1, len(A)):
    left_product[i] = left_product[i - 1] * A[i - 1]
  for i in xrange(len(A) - 2, -1, -1):
    right_product[i] = right_product[i + 1] * A[i + 1]
  B = [1] * len(A)
  for i in xrange(len(A)):
    B[i] = left_product[i] * right_product[i]
  return B
assert(solve([1, 7, 3, 4]) == [84, 12, 28, 21])

Khi đọc kỹ đoạn mã trên, ta sẽ thấy rằng có lẽ danh sách left_product là thừa. Thay vào đó, trong quá trình tính B, ta có thể giữ một biến tạm cho biết tích từ A[0] đến A[i - 1]. Phần này xin được dành làm một thử thách nhỏ cho bạn đọc. Nếu bạn giải ra, xin hãy cùng trao đổi trong diễn đàn.