數組乘積問題：不使用除法計算除自身以外所有元素的乘積

問題描述

給定數組 a[N]，構造數組 b[N]，使得 b[i] = a[0]*a[1]*...*a[N-1] / a[i]。
限制條件：
1. **不准使用除法**
2. 除循環變量、a、b 外，**不准使用任何額外變量**（含局部/全局）
3. 時間 O(N)，空間 O(1)

核心思路：左右乘積分解

b[i] 等價於 (a[0]...a[i-1]) * (a[i+1]...a[N-1])。定義：
- left[i] = a[0]*...*a[i-1]（i 左側乘積）
- right[i] = a[i+1]*...*a[N-1]（i 右側乘積）
則 b[i] = left[i] * right[i]。

可用 b 數組本身暫存中間結果，兩次掃描完成：

1. **正向掃描**：b[0] = 1；對 i=1..N-1，b[i] = b[i-1] * a[i-1]。此時 b[i] 存的是 left[i]。
2. **反向掃描**：用一個臨時變量（復用 b[0]）累積 right 乘積。從 N-2 降到 0，b[0] *= a[i+1]，b[i] *= b[0]。
3. 最後單獨處理 b[0] = a[1] * b[0]。

代碼實現

#include <stdio.h>
#include <stdlib.h>

void Multiplication(int *a, int *b, int length) {
    int i;
    b[0] = 1;
    for (i = 1; i < length; i++) {
        b[0] *= a[i - 1];
        b[i] = b[0];
    }
    b[0] = 1;
    for (i = length - 2; i > 0; i--) {
        b[0] *= a[i + 1];
        b[i] *= b[0];
    }
    b[0] = a[1] * b[0];
}

int main() {
    int i;
    int a[] = {2, 2, 3, 4, 5};
    int b[5];
    int length = sizeof(a) / sizeof(int);
    Multiplication(a, b, length);
    for (i = 0; i < length; i++) printf("%d\t", b[i]);
    return 0;
}

執行trace (a=[2,2,3,4,5])

關鍵技巧

• **輸出數組複用作中間存儲** — 滿足 O(1) 額外空間。
• **b[0] 復用為右側乘積累積器** — 避免額外變量。
• **邊界單獨處理** — 正向從 1 開始，反向到 1 結束，b[0] 最後計算。

複雜度

• 時間：O(N) — 兩次線性掃描。
• 空間：O(1) — 僅用輸出數組與常數變量。