Given an array nums[] of size n, construct a Product Array P (of same size n) such that P[i] is equal to the product of all the elements of nums except nums[i].
 
Example 1:
Input:
n = 5
nums[] = {10, 3, 5, 6, 2}
Output:
180 600 360 300 900
Explanation: 
For i=0, P[i] = 3*5*6*2 = 180.
For i=1, P[i] = 10*5*6*2 = 600.
For i=2, P[i] = 10*3*6*2 = 360.
For i=3, P[i] = 10*3*5*2 = 300.
For i=4, P[i] = 10*3*5*6 = 900.
Example 2:
Input:
n = 2
nums[] = {12,0}
Output:
0 12
Your Task:
You do not have to read input. Your task is to complete the function productExceptSelf() that takes array nums[] and n as input parameters and returns a list of n integers denoting the product array P. If the array has only one element the returned list should should contains one value i.e {1}
Note: Try to solve this problem without using the division operation.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
 
Constraints:
1 <= n <= 1000
0 <= nums_{i} <= 200
Array may contain duplicates.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def productExceptSelf(self, nums, n):
        #code here

Solutions:
class Solution:

	def productExceptSelf(self, nums, n):
		prefix = [1] * n
		suffix = [1] * n
		for i in range(1, n):
			prefix[i] = prefix[i - 1] * nums[i - 1]
		for i in range(n - 2, -1, -1):
			suffix[i] = suffix[i + 1] * nums[i + 1]
		P = [prefix[i] * suffix[i] for i in range(n)]
		return P


from functools import reduce
from operator import mul

class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			return [1]
		left = [nums[0]] * len(nums)
		right = [nums[-1]] * len(nums)
		for i in range(1, len(nums)):
			left[i] = left[i - 1] * nums[i]
			right[len(nums) - i - 1] = right[len(nums) - i] * nums[len(nums) - i - 1]
		result = [0] * len(nums)
		(result[0], result[-1]) = (right[1], left[-2])
		for i in range(1, len(nums) - 1):
			result[i] = left[i - 1] * right[i + 1]
		return result


class Solution:

	def productExceptSelf(self, nums, n):
		beg = [1] * n
		for i in range(1, n):
			beg[i] = nums[i - 1] * beg[i - 1]
		last = [1] * n
		for i in range(n - 2, -1, -1):
			last[i] = last[i + 1] * nums[i + 1]
		for i in range(n):
			beg[i] *= last[i]
		return beg


class Solution:

	def solve1(self, nums, n):
		product = 1
		zero_cnt = 0
		zero_idx = -1
		for (i, num) in enumerate(nums, start=0):
			if num == 0:
				zero_cnt += 1
				zero_idx = i
			else:
				product *= num
		ans = [0] * n
		if zero_cnt >= 2:
			return ans
		if zero_cnt == 1:
			ans[zero_idx] = product
			return ans
		for (i, num) in enumerate(nums, start=0):
			ans[i] = product // num
		return ans

	def solve(self, nums, n):
		left = [1] * n
		right = [1] * n
		for i in range(1, n):
			left[i] = left[i - 1] * nums[i - 1]
		for i in range(n - 2, -1, -1):
			right[i] = right[i + 1] * nums[i + 1]
		for i in range(n):
			nums[i] = left[i] * right[i]
		return nums

	def productExceptSelf(self, nums, n):
		return self.solve1(nums, n)


class Solution:

	def productExceptSelf(self, nums, n):
		res = [1] * len(nums)
		prefix = 1
		for i in range(len(nums)):
			res[i] = prefix
			prefix *= nums[i]
		postfix = 1
		for i in range(len(nums) - 1, -1, -1):
			res[i] *= postfix
			postfix *= nums[i]
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		max_product = 1
		flag = False
		count = 0
		for i in range(n):
			if nums[i] != 0:
				max_product = max_product * nums[i]
			else:
				flag = True
				count += 1
		if count > 1:
			for i in range(n):
				nums[i] = 0
		else:
			for i in range(n):
				if nums[i] == 0:
					nums[i] = max_product
				elif flag == True:
					nums[i] = 0
				else:
					nums[i] = max_product // nums[i]
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		ans = []
		left = [1] * n
		right = [1] * n
		for i in range(1, n):
			left[i] = left[i - 1] * nums[i - 1]
		for i in range(n - 2, -1, -1):
			right[i] = right[i + 1] * nums[i + 1]
		for i in range(n):
			nums[i] = left[i] * right[i]
		return nums


import copy

class Solution:

	def productExceptSelf(self, nums, n):
		l = []
		c = 1
		for i in nums:
			c = c * i
		for i in nums:
			if i > 0 or i < 0:
				l.append(c // i)
			elif i == 0:
				l1 = copy.deepcopy(nums)
				l1.remove(i)
				l1 = map(str, l1)
				c1 = eval('*'.join(l1))
				l.append(c1)
		return l


class Solution:

	def productExceptSelf(self, nums, n):
		noOfZeros = 0
		prod = 1
		for num in nums:
			if num == 0:
				noOfZeros += 1
				continue
			prod *= num
		ans = []
		if noOfZeros > 1:
			j = 0
			while j < n:
				ans.append(0)
				j += 1
			return ans
		elif noOfZeros == 1:
			j = 0
			while j < n:
				if nums[j] == 0:
					ans.append(prod)
				else:
					ans.append(0)
				j += 1
			return ans
		i = 0
		while i < n:
			ans.append(prod // nums[i])
			i += 1
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		var = 1
		product1 = [1] * n
		for i in range(1, n):
			var *= nums[i - 1]
			product1[i] = var
		var = 1
		product2 = [1] * n
		for i in range(n - 2, -1, -1):
			var *= nums[i + 1]
			product2[i] = var
		for i in range(n):
			product1[i] *= product2[i]
		return product1


class Solution:

	def productExceptSelf(self, nums, n):
		zc = nums.count(0)
		if zc > 1:
			return [0] * n
		p = 1
		for i in range(0, n):
			if nums[i] != 0:
				p *= nums[i]
		ans = []
		for i in nums:
			if i != 0:
				ans.append(0 if zc == 1 else p // i)
			else:
				ans.append(p)
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		prod = 1
		flag = False
		flag2 = False
		if 0 in nums:
			flag = True
		if nums.count(0) > 1:
			flag2 = True
		if flag2:
			return [0] * n
		if flag:
			for i in nums:
				if i != 0:
					prod *= i
		else:
			for i in nums:
				prod *= i
		res = []
		if flag:
			for i in nums:
				if i == 0:
					res.append(prod)
				else:
					res.append(0)
		else:
			for i in nums:
				res.append(round(prod * i ** (-1)))
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		a = arr.count(0)
		if a == 0:
			prdct = 1
			for i in nums:
				prdct = prdct * i
			ans = [1] * n
			for i in range(n):
				ans[i] = int(prdct / arr[i])
			return ans
		if a > 1:
			return [0] * n
		prdct = 1
		for i in nums:
			if i != 0:
				prdct = prdct * i
		ans = [1] * n
		for i in range(n):
			if arr[i] == 0:
				ans[i] = prdct
			else:
				ans[i] = 0
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		l = []
		if 0 not in nums:
			p = 1
			for i in nums:
				p = p * i
			for i in nums:
				l.append(p // i)
		else:
			p = 1
			for i in nums:
				if i != 0:
					p = p * i
			for i in nums:
				if i == 0:
					if nums.count(0) > 1:
						l.append(0)
					else:
						l.append(p)
				else:
					l.append(0)
		return l


class Solution:

	def productExceptSelf(self, nums, n):
		prod = [1]
		for i in range(1, len(nums)):
			prod.append(prod[i - 1] * nums[i - 1])
		right = 1
		for i in range(len(nums) - 1, -1, -1):
			prod[i] *= right
			right *= nums[i]
		return prod


class Solution:

	def productExceptSelf(self, nums, n):
		list1 = []
		if nums.count(0) > 1:
			return [0] * n
		if nums.count(0) == 1:
			index = nums.index(0)
			nums.remove(0)
			product = 1
			for i in nums:
				product *= i
			for i in range(n):
				if i == index:
					list1.append(product)
				else:
					list1.append(0)
			return list1
		else:
			product = 1
			for i in nums:
				product *= i
			for i in nums:
				list1.append(product // i)
		return list1


class Solution:

	def productExceptSelf(self, nums, n):
		mult = 1
		mult_ = 1
		c = arr.count(0)
		for i in range(n):
			if nums[i] == 0:
				if c == 1:
					mult_ = mult_
				else:
					mult_ = 0
			elif nums[i] != 0:
				mult_ = mult_ * nums[i]
			mult = mult * nums[i]
		for i in range(n):
			if nums[i] != 0:
				nums[i] = mult // nums[i]
			elif nums[i] == 0:
				nums[i] = mult_
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			return [1]
		product = 1
		count_map = {}
		for num in nums:
			if num != 0:
				product *= num
			elif num in count_map:
				count_map[num] = count_map[num] + 1
			else:
				count_map[num] = 1
		products = []
		for num in nums:
			if num == 0:
				if count_map[num] == 1:
					products.append(product)
				else:
					products.append(0)
			elif 0 in count_map:
				products.append(0)
			else:
				products.append(product // num)
		return products


class Solution:

	def productExceptSelf(self, nums, n):
		dp = [1 for i in range(n)]
		for i in range(1, n):
			dp[i] = nums[i - 1] * dp[i - 1]
		product = nums[-1]
		for j in range(n - 2, -1, -1):
			dp[j] *= product
			product *= nums[j]
		return dp


class Solution:

	def productExceptSelf(self, nums, n):
		output = [1]
		for i in range(n - 1, 0, -1):
			output.append(output[-1] * nums[i])
		output = output[::-1]
		left = 1
		for i in range(n):
			output[i] = output[i] * left
			left *= nums[i]
		return output


class Solution:

	def productExceptSelf(self, nums, n):
		n = len(nums)
		left = [0] * n
		left[0] = 1
		for i in range(1, n):
			left[i] = left[i - 1] * nums[i - 1]
		right = 1
		P = [0] * n
		for i in range(n - 1, -1, -1):
			P[i] = left[i] * right
			right *= nums[i]
		return P


import numpy as np
import math

class Solution:

	def productExceptSelf(self, nums, n):
		list1 = []
		if nums.count(0) > 1:
			return [0] * n
		elif nums.count(0) == 1:
			index_zero = nums.index(0)
			nums.remove(0)
			product = np.prod(np.array(nums))
			for i in range(n):
				if i == index_zero:
					list1.append(product)
				else:
					list1.append(0)
		else:
			product = np.prod(np.array(nums))
			for i in range(n):
				list1.append(product // nums[i])
		return list1


class Solution:

	def productExceptSelf(self, nums, n):
		ans = []
		prod = 1
		flag = 0
		count = 0
		for i in nums:
			if i != 0:
				prod *= i
			else:
				flag = 1
				count += 1
		if flag == 1 and count == 1:
			for i in nums:
				if i != 0:
					ans.append(0)
				else:
					ans.append(int(prod))
			return ans
		elif flag == 1 and count > 1:
			for i in nums:
				ans.append(0)
			return ans
		for i in nums:
			ans.append(int(prod / i))
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		total = 1
		tracks = 0
		for i in nums:
			if i == 0:
				tracks += 1
				continue
			total *= i
		for i in range(n):
			if tracks > 1 or (tracks == 1 and nums[i] != 0):
				nums[i] = 0
			elif tracks == 0:
				nums[i] = total // nums[i]
			else:
				nums[i] = total
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		ans = [1] * n
		prod = 1
		for i in range(1, n):
			prod = prod * nums[i - 1]
			ans[i] = prod
		prod = nums[-1]
		for i in range(n - 2, -1, -1):
			ans[i] = prod * ans[i]
			prod = prod * nums[i]
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			return [1]
		res = []
		l = []
		r = [0] * n
		tmp = 1
		for i in nums:
			tmp = tmp * i
			l.append(tmp)
		tmp = 1
		for i in range(n - 1, -1, -1):
			tmp *= nums[i]
			r[i] = tmp
		res.append(r[1])
		for i in range(1, n):
			if i == n - 1:
				res.append(l[i - 1])
			else:
				res.append(l[i - 1] * r[i + 1])
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		counter = arr.count(0)
		if counter >= 2:
			return [0 for i in range(len(arr))]
		product = 1
		res = []
		for i in range(len(arr)):
			if arr[i] == 0:
				arr[i] = 1
				product *= arr[i]
				arr[i] = 0
				continue
			product *= arr[i]
		if counter == 1:
			temp = 0
			for i in range(len(arr)):
				if arr[i] == 0:
					temp = product
					res.append(temp)
					temp = 0
					continue
				res.append(temp)
			return res
		for i in range(len(arr)):
			res.append(product // arr[i])
		return res


class Solution:

	def if_zero(self, arr):
		num1 = 1
		count = 0
		for i in range(len(arr)):
			temp1 = arr[i]
			if arr[i] == 0:
				temp1 = 1
				count = count + 1
				if count == 2:
					return 0
			num1 = num1 * temp1
		return num1

	def productExceptSelf(self, arr, n):
		l = []
		num = 1
		extra = self.if_zero(arr)
		for i in range(n):
			num = num * arr[i]
		for i in range(n):
			try:
				temp = num // arr[i]
			except:
				temp = extra
			l.append(temp)
		return l


class Solution:

	def productExceptSelf(self, nums, n):
		res = [1] * n
		pre = 1
		post = 1
		for i in range(n):
			res[i] *= pre
			pre *= nums[i]
		for i in range(n - 1, -1, -1):
			res[i] *= post
			post *= nums[i]
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		result = [1] * n
		l_pro = 1
		for i in range(n):
			result[i] *= l_pro
			l_pro *= nums[i]
		r_pro = 1
		for i in range(n - 1, -1, -1):
			result[i] *= r_pro
			r_pro *= nums[i]
		return list(result)


class Solution:

	def productExceptSelf(self, nums, n):
		arr = []
		pref = post = 1
		for i in range(len(nums)):
			arr.append(pref)
			pref *= nums[i]
		for i in range(len(nums) - 1, -1, -1):
			arr[i] *= post
			post *= nums[i]
		return arr


import math

class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			return '1'
		left = [0] * n
		right = [0] * n
		prod = [0] * n
		left[0] = 1
		right[n - 1] = 1
		for i in range(1, n):
			left[i] = nums[i - 1] * left[i - 1]
		for j in range(n - 2, -1, -1):
			right[j] = nums[j + 1] * right[j + 1]
		for i in range(n):
			prod[i] = left[i] * right[i]
		return prod


class Solution:

	def productExceptSelf(self, nums, n):
		res = 1
		r = []
		c = 0
		for i in nums:
			if i == 0:
				c += 1
			if c >= 2:
				for i in nums:
					r.append(0)
				return r
		for i in nums:
			if i != 0:
				res *= i
		if 0 in nums:
			for i in nums:
				if i == 0:
					r.append(res)
				else:
					r.append(0)
		else:
			for i in nums:
				if i != 0:
					r.append(int(res / i))
		return r


class Solution:

	def productExceptSelf(self, nums, n):
		psum = 1
		c = 0
		k = []
		for i in range(n):
			if nums[i] == 0:
				c += 1
				continue
			else:
				psum *= nums[i]
		if c == 0:
			for i in range(n):
				tmp = psum // nums[i]
				k.append(tmp)
			return k
		elif c > 1:
			for i in range(n):
				k.append(0)
			return k
		elif c == 1:
			for i in range(n):
				if nums[i] != 0:
					k.append(0)
				else:
					k.append(psum)
			return k


class Solution:

	def productExceptSelf(self, nums, n):
		p = [1 for i in nums]
		temp = 1
		for i in range(0, n):
			p[i] = temp * p[i]
			temp = temp * nums[i]
		temp = 1
		for i in range(n - 1, -1, -1):
			p[i] = temp * p[i]
			temp = temp * nums[i]
		return p


import math

class Solution:

	def productExceptSelf(self, arr, n):
		res = []
		p = 1
		for i in range(n):
			p *= arr[i]
			res.append(p)
		p = 1
		for i in range(n - 1, 0, -1):
			res[i] = res[i - 1] * p
			p *= arr[i]
		res[0] = p
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			return [1]
		if n == 2:
			return [nums[1], nums[0]]
		sp = [1] * n
		ep = [1] * n
		p1 = 1
		p2 = 1
		for i in range(n):
			p1 *= nums[i]
			p2 *= nums[n - 1 - i]
			sp[i] = p1
			ep[n - 1 - i] = p2
		res = [1] * n
		res[0] = ep[1]
		res[n - 1] = sp[n - 2]
		for i in range(1, n - 1):
			res[i] = sp[i - 1] * ep[i + 1]
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		p = 1
		x = 0
		y = 1
		for i in range(n):
			p = p * nums[i]
			if nums[i] == 0:
				x += 1
			else:
				y = y * nums[i]
		arr = []
		for i in range(n):
			if nums[i] == 0 and x == 1:
				arr.append(y)
			elif nums[i] == 0:
				arr.append(0)
			else:
				arr.append(int(p / nums[i]))
		return arr


class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			return [1]
		(i, temp) = (1, 1)
		prod = [1 for i in range(n)]
		for i in range(n):
			prod[i] = temp
			temp *= arr[i]
		temp = 1
		for i in range(n - 1, -1, -1):
			prod[i] *= temp
			temp *= arr[i]
		return prod


class Solution:

	def productExceptSelf(self, nums, n):
		d = {}
		for i in nums:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		if 0 in d and d[0] > 1:
			ans = [0] * n
			return ans
		productofall = 1
		prodforzero = 1
		for i in nums:
			productofall *= i
			if i == 0:
				i = 1
			prodforzero *= i
		ans = []
		for i in nums:
			if i == 0:
				ans.append(prodforzero)
			else:
				ans.append(productofall // i)
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		prod = 1
		zeroes = 0
		for i in nums:
			if i == 0:
				zeroes += 1
				continue
			else:
				prod *= i
		if zeroes > 1:
			return [0] * n
		parr = []
		if zeroes == 1:
			for i in arr:
				if i == 0:
					parr.append(prod)
				else:
					parr.append(0)
		else:
			for i in arr:
				parr.append(prod // i)
		return parr


class Solution:

	def productExceptSelf(self, nums, n):
		p = 1
		q = 0
		if len(nums) == 2:
			(nums[0], nums[1]) = (nums[1], nums[0])
			return nums
		for i in nums:
			if i == 0:
				q = q + 1
			else:
				p = p * i
		for (i, j) in enumerate(nums):
			if q == 1:
				if j == 0:
					nums[i] = p
				else:
					nums[i] = 0
			elif q > 1:
				nums[i] = 0
			else:
				nums[i] = int(p / nums[i])
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		i = 0
		w = 0
		c = 1
		l = []
		while i < n:
			if nums[i] == 0:
				w = w + 1
				i = i + 1
				continue
			c = c * nums[i]
			i = i + 1
		i = 0
		while i < n:
			if w >= 1:
				if w > 1:
					l.append(0)
					i = i + 1
					continue
				if nums[i] != 0:
					l.append(0)
					i = i + 1
					continue
				else:
					l.append(c)
					i = i + 1
					continue
			p = int(c / nums[i])
			l.append(p)
			i = i + 1
		return l


class Solution:

	def productExceptSelf(self, nums, n):
		p = 1
		for i in nums:
			p *= i
		r = []
		c = nums.count(0)
		for i in range(n):
			if nums[i] == 0:
				if c == 1:
					p1 = 1
					for j in range(n):
						if j == i:
							continue
						p1 *= nums[j]
					r.append(p1)
				else:
					r.append(0)
			else:
				r.append(p // nums[i])
		return r


class Solution:

	def productExceptSelf(self, nums, n):
		prod = 1
		flag = 0
		for i in range(n):
			if nums[i] == 0:
				flag += 1
			else:
				prod *= nums[i]
		arr = [0 for i in range(n)]
		for i in range(n):
			if flag > 1:
				arr[i] = 0
			elif flag == 0:
				arr[i] = prod // nums[i]
			elif flag == 1 and nums[i] != 0:
				arr[i] = 0
			else:
				arr[i] = prod
		return arr


class Solution:

	def productExceptSelf(self, nums, n):
		list1 = list()
		k = 1
		for i in nums:
			if i != 0:
				k *= i
		if nums.count(0) > 1:
			return [0] * n
		elif nums.count(0) == 1:
			indi = nums.index(0)
			nums.remove(0)
			for i in range(n):
				if i == indi:
					list1.append(k)
				else:
					list1.append(0)
		else:
			for i in nums:
				list1.append(k // i)
		return list1


class Solution:

	def productExceptSelf(self, nums, n):
		brr = []
		mul = 1
		count = 0
		for i in nums:
			mul = mul * i
			if i == 0:
				count += 1
		if count >= 2:
			for i in range(n):
				brr.append(0)
			return brr
		elif count == 1:
			mul2 = 1
			for i in nums:
				if i != 0:
					mul2 = mul2 * i
			for i in range(0, n):
				brr.append(0)
			brr[arr.index(0)] = mul2
			return brr
		else:
			for i in range(0, n):
				brr.append(mul // arr[i])
			return brr


class Solution:

	def productExceptSelf(self, nums, n):
		overall = 1
		if_zero = 0
		prod = []
		for num in nums:
			if num != 0:
				overall *= num
			else:
				if_zero += 1
		if if_zero > 1:
			return [0] * n
		for num in nums:
			if num:
				prod.append(0 if if_zero else overall // num)
			else:
				prod.append(overall)
		return prod


class Solution:

	def productExceptSelf(self, nums, n):
		p = 1
		P = []
		count = 0
		for i in range(n):
			if nums[i] == 0:
				count += 1
		for i in range(n):
			if nums[i] != 0 and count < 2:
				p = p * nums[i]
		for i in range(n):
			if count == 0:
				P.append(round(p / nums[i]))
			elif count == 1:
				if nums[i] == 0:
					P.append(p)
				else:
					P.append(0)
			else:
				P.append(0)
		return P


class Solution:

	def productExceptSelf(self, nums, n):
		mul = 1
		count0 = 0
		for i in nums:
			if i != 0:
				mul *= i
			else:
				count0 += 1
		if count0 == 0:
			for i in range(n):
				nums[i] = mul // nums[i]
		elif count0 == 1:
			for i in range(n):
				if nums[i] != 0:
					nums[i] = 0
				else:
					nums[i] = mul
		else:
			for i in range(n):
				nums[i] = 0
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		prod = 1
		newarr = [0 for x in range(n)]
		for i in nums:
			prod *= i
		for x in range(n):
			try:
				newarr[x] = prod // nums[x]
			except:
				if nums.count(0) > 1:
					newarr[x] = 0
				else:
					nuz = nums.copy()
					nuz.remove(0)
					zer = 1
					for i in nuz:
						zer *= i
					newarr[x] = zer
		return newarr


class Solution:

	def productExceptSelf(self, nums, n):
		left = []
		right = []
		for i in range(n):
			left.append(-1)
			right.append(-1)
		left[0] = 1
		right[n - 1] = 1
		(manu, sid) = (1, 1)
		for i in range(n - 1):
			manu = manu * nums[i]
			left[i + 1] = manu
		for i in range(n - 1, 0, -1):
			sid = sid * nums[i]
			right[i - 1] = sid
		ans = []
		for i in range(n):
			ans.append(left[i] * right[i])
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		ans = [1 for i in range(n)]
		pre = 1
		for (i, j) in enumerate(nums):
			ans[i] *= pre
			pre *= j
		post = 1
		for i in range(len(nums) - 1, -1, -1):
			ans[i] *= post
			post *= nums[i]
		for (i, j) in enumerate(ans):
			nums[i] = j
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			nums[0] = 1
			return nums
		left = [0] * n
		right = [0] * n
		left[0] = nums[0]
		right[-1] = nums[-1]
		for i in range(1, n):
			left[i] = nums[i] * left[i - 1]
			right[n - i - 1] = nums[n - i - 1] * right[n - i]
		for i in range(n):
			if i == 0:
				nums[i] = right[i + 1]
			elif i == n - 1:
				nums[i] = left[i - 1]
			else:
				nums[i] = left[i - 1] * right[i + 1]
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		lst1 = []
		if n == 1:
			lst1.append(1)
			return lst1
		prod = 1
		for i in range(0, n):
			if nums[i] == 0:
				continue
			else:
				prod = prod * nums[i]
		lst = []
		for i in nums:
			if 0 in nums:
				if nums.count(0) > 1:
					return [0] * n
				elif i == 0:
					lst.append(prod)
				else:
					lst.append(0)
			else:
				val = prod // i
				lst.append(val)
		return lst


import numpy as np

class Solution:

	def productExceptSelf(self, nums, n):
		list1 = list()
		if nums.count(0) > 1:
			return [0] * n
		elif nums.count(0) == 1:
			indi = nums.index(0)
			nums.remove(0)
			k = np.prod(np.array(nums))
			for i in range(n):
				if i == indi:
					list1.append(k)
				else:
					list1.append(0)
		else:
			k = np.prod(np.array(nums))
			for i in nums:
				list1.append(k // i)
		return list1


class Solution:

	def productExceptSelf(self, nums, n):
		li = [0] * n
		ri = [0] * n
		li[0] = 1
		ri[n - 1] = 1
		for i in range(1, n):
			li[i] = li[i - 1] * nums[i - 1]
		for j in range(n - 2, -1, -1):
			ri[j] = ri[j + 1] * nums[j + 1]
		for i in range(0, n):
			nums[i] = li[i] * ri[i]
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		if len(nums) == 1:
			return [1]
		left = []
		right = []
		pr = 1
		for i in range(n):
			pr = pr * nums[i]
			left.append(pr)
		pr = 1
		for j in range(n - 1, -1, -1):
			pr = pr * nums[j]
			right.append(pr)
		right = right[::-1]
		for i in range(n):
			if i == 0:
				nums[i] = right[i + 1]
			elif i == n - 1:
				nums[i] = left[i - 1]
			else:
				nums[i] = left[i - 1] * right[i + 1]
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		product = 1
		extra_product = 1
		nums_zero = 0
		for index in range(n):
			if nums[index] != 0:
				extra_product *= nums[index]
			if nums[index] == 0:
				nums_zero += 1
			product *= nums[index]
		if nums_zero > 1:
			return [0 for index in range(n)]
		ans = []
		for index in range(n):
			if nums[index] == 0:
				ans.append(extra_product)
			else:
				ans.append(product // nums[index])
		return ans


class Solution:

	def productExceptSelf(self, nums, n):
		left = [None] * (n + 1)
		left[0] = 1
		right = [None] * (n + 1)
		right[n - 1] = 1
		p = [None] * n
		for i in range(1, n):
			left[i] = left[i - 1] * nums[i - 1]
		for i in range(n - 2, -1, -1):
			right[i] = right[i + 1] * nums[i + 1]
		for i in range(0, n):
			p[i] = left[i] * right[i]
		return p


class Solution:

	def productExceptSelf(self, nums, n):
		prod = 1
		z = 0
		for i in nums:
			if i == 0:
				z += 1
				i = 1
			prod *= i
		l = []
		if z > 1:
			return [0] * n
		for i in nums:
			if z > 0:
				if i == 0:
					l.append(prod)
				else:
					l.append(0)
			else:
				l.append(prod // i)
		return l


class Solution:

	def productExceptSelf(self, nums, n):
		left = [0] * n
		right = [0] * n
		product = [0] * n
		left[0] = 1
		right[n - 1] = 1
		for i in range(1, n):
			left[i] = left[i - 1] * nums[i - 1]
		for j in range(n - 2, -1, -1):
			right[j] = right[j + 1] * nums[j + 1]
		for i in range(n):
			product[i] = left[i] * right[i]
		return product


class Solution:

	def productExceptSelf(self, nums, n):
		l = []
		if n == 1:
			l.append(1)
			return l
		pro = 1
		for i in range(n):
			if nums[i] == 0:
				continue
			else:
				pro = pro * nums[i]
		lst = []
		for i in nums:
			if 0 in nums:
				if nums.count(0) > 1:
					return [0] * n
				elif i == 0:
					l.append(pro)
				else:
					l.append(0)
			else:
				val = pro // i
				l.append(val)
		return l


class Solution:

	def productExceptSelf(self, arr, n):
		left = []
		right = []
		prod = 1
		for elm in arr:
			left.append(prod)
			prod *= elm
		prod = 1
		for i in range(n - 1, -1, -1):
			right.append(prod)
			prod *= arr[i]
		right = right[::-1]
		for i in range(n):
			arr[i] = left[i] * right[i]
		return arr


class Solution:

	def productExceptSelf(self, nums, n):
		P = [1] * n
		left = 1
		for i in range(1, n):
			left = left * arr[i - 1]
			P[i] *= left
		right = 1
		for i in range(n - 2, -1, -1):
			right = right * arr[i + 1]
			P[i] *= right
		return P


class Solution:

	def productExceptSelf(self, nums, n):
		res = []
		mul = 1
		zero = 0
		for i in range(0, n):
			if nums[i] == 0:
				zero = zero + 1
			else:
				mul = mul * nums[i]
		for i in range(0, n):
			if nums[i] == 0 and zero == 1:
				res.append(mul)
			elif zero == 1 and nums[i] != 0:
				res.append(0)
			elif zero > 1:
				res.append(0)
			else:
				ans = mul // nums[i]
				res.append(ans)
		return res


class Solution:

	def productExceptSelf(self, nums, n):
		product = 1
		prodctwithzero = -1
		for i in nums:
			if i == 0:
				prodctwithzero += 1
			else:
				product *= i
		for i in range(len(nums)):
			if prodctwithzero > 0:
				nums[i] = 0
			elif prodctwithzero > -1:
				if nums[i] == 0:
					nums[i] = product
				elif nums[i] >= 1:
					nums[i] = 0
				else:
					nums[i] = 0
			else:
				nums[i] = product // nums[i]
		return nums


class Solution:

	def productExceptSelf(self, nums, n):
		if n == 1:
			p = [1]
		else:
			p = [1]
			r = [1]
			for i in range(1, n):
				p.append(p[i - 1] * nums[i - 1])
				r.insert(-i - 1, r[-i] * nums[-i])
			for i in range(n):
				p[i] = p[i] * r[i]
		return p


class Solution:

	def productExceptSelf(self, nums, n):
		total = 1
		count = 0
		for i in nums:
			if i == 0:
				count += 1
			else:
				total *= i
		P = []
		if count > 1:
			P = [0] * n
		elif count == 1:
			for i in range(n):
				if nums[i] == 0:
					P.append(total)
				else:
					P.append(0)
		else:
			for i in range(n):
				P.append(total // nums[i])
		return P


from functools import reduce

class Solution:

	def productExceptSelf(self, nums, n):
		prod = reduce(lambda x, y: x * y, nums)
		s = []
		for i in range(n):
			try:
				s.append(prod // nums[i])
			except:
				li = nums.copy()
				li.pop(i)
				prod1 = reduce(lambda x, y: x * y, li)
				s.append(prod1)
		return s


class Solution:

	def productExceptSelf(self, nums, n):
		a = []
		if n == 1:
			return [1]
		p = 1
		for i in range(n):
			p *= arr[i]
			a.append(p)
		product = 1
		for i in range(n - 1, 0, -1):
			if i == n - 1:
				a[i] = a[i - 2]
			a[i] = a[i - 1] * product
			product *= nums[i]
		a[0] = product
		return a