> For the complete documentation index, see [llms.txt](https://quenluo.gitbook.io/leecode-python/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://quenluo.gitbook.io/leecode-python/238.-product-of-array-except-self.md).

# 238. Product of Array Except Self

## Question 238

<https://leetcode.com/problems/product-of-array-except-self/description/>

Given an array `nums` of *n* integers where *n* > 1,  return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

**Example:**

```
Input:  [1,2,3,4]
Output: [24,12,8,6]
```

**Note:** Please solve it **without division** and in O(*n*).

## Answer

### **v1. multiply two lists (70.66%)**

1. 產生兩種 list 分別是由右累乘到左以及左累乘到右\
   input => \[a,b,c,d]

   由右累乘 => \[1,d,cd,cdb,cdba]

   由左累乘 => \[1,a,ab,abc,abcd]
2. 將兩條 list 相乘\
   \[cdb\*1 ,cd\*a ,d\*ab ,1\*abc]

### **v2. multiply two times (84.95%)**

1. 初始化 output list 使其皆為 1&#x20;
2. 於第一個迴圈將由左至右累乘的數字存進 output list 中\
   其第一個值為 1 (預設)
3. 於第二個迴圈將由左至右累乘的數字乘進原本的 output list 中

{% tabs %}
{% tab title="v1" %}

```python
class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def productExceptSelf(self, nums):
        
        # count len of nums[]
        n = len(nums)
        
        output = []
        left2right=[]
        right2left=[]
        tmpnumL = 1
        tmpnumR = 1
        
        # multiply left to right and right to left
        for i in range(0,n):
            left2right.append(tmpnumL)
            tmpnumL = tmpnumL * nums[i]
            
            right2left.append(tmpnumR)
            tmpnumR = tmpnumR * nums[(n-1)-i]
            

        # multiply each
        for i in range(0,n):
            output.append( right2left[(n-1)-i] * left2right[i] )
        
        return output
```

{% endtab %}

{% tab title="v2" %}

```python
class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def productExceptSelf(self, nums):
        
        # count len of nums[]
        n = len(nums)
        
        output = [1] * n
        tmpnumL = 1
        tmpnumR = 1
        
        # multiply left to right
        for i in range(0,n-1):
            tmpnumL = tmpnumL * nums[i]
            output[i+1] = tmpnumL
            
        # multiply right to left
        for i in range((n-1),0,-1):
            tmpnumR = tmpnumR * nums[i]
            output[i-1] *= tmpnumR 
        
        return output
```

{% endtab %}
{% endtabs %}