You are given an integer array nums. Build a new array answer of the same length.
answer[i] must be the product of all the numbers in nums except nums[i].
Do not use division. Your code must run in O(n) time.
You can be sure that the product of any prefix (the first few numbers) or any suffix (the last few numbers) of nums fits in a 32-bit integer.
Examples
Example 1:
Input: nums = [2,3,4]
Output: [12,8,6]
Explanation: For index 0 we multiply 3 * 4 = 12. For index 1 we multiply 2 * 4 = 8. For index 2 we multiply 2 * 3 = 6.
Example 2:
Input: nums = [3,0,2,5]
Output: [0,30,0,0]
Explanation: Any product that includes the 0 is 0. Only the place of the 0 gets a bigger value: 3 * 2 * 5 = 30.
Example 3:
Input: nums = [-2,5,-1,1]
Output: [-5,2,-10,10]
Explanation: Signs follow the normal rules. For index 2 we multiply -2 * 5 * 1 = -10.