# Simple Java solution in O(n) without extra space

• ``````public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
``````

}

• This post is deleted!

• how do you get this amazing idea?

• This post is deleted!

• another amazing idea, which I saw on stackoverflow.
http://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div/2696005#2696005

``````int multiply(int *a, int fwdProduct, int indx) {
int revProduct = 1;
if (indx < N) {
revProduct = multiply(a, fwdProduct*a[indx], indx+1);
int cur = a[indx];
a[indx] = fwdProduct * revProduct;
revProduct *= cur;
}
return revProduct;
}``````

• This post is deleted!

• Great solution! Thanks for your sharing. I think the first answer in this link gives a nice illustration of your idea. I rewrite the code in C++ below.

``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> prod(n, 1);
for (int i = 1; i < n; i++)
prod[i] = prod[i - 1] * nums[i - 1];
for (int i = n - 1, r = 1; i >= 0; r *= nums[i--])
prod[i] *= r;
return prod;
}
};
``````

• length == 1 is not considered, but that also makes no sense, so ignore my comment.

• "without extra space"? I see `n`, `i` and `right`.

• Great. I wrote a simpler one in C++.

``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res(nums.size(),1);
for(int i=0,j=nums.size()-1, tmp1=1, tmp2=1;i<nums.size();++i,--j) {
res[i]*=tmp1, tmp1*=nums[i];
res[j]*=tmp2, tmp2*=nums[j];
}
return res;
}
};``````

• dude this is JI ZHI

• Wow you are unbelievable.

• That is really Amazing!

• awesome space saving idea. truely jizhi

• This is brilliant!!!

• Thank you ! But I don't know whether creating a new array doesn't mean "without extra space"?

• i dnt think it's a simpler one，for both human and machine ^_^

• The problem description said: "The output array does not count as extra space for the purpose of space complexity analysis."

• This is amazingly brilliant !!!

• I have another way.I think it's the same as yours in the aspect that is without extra space.The time is O(n),too.
This is my code:
public static int[] productExceptSelf(int[] nums) {
int[] output = new int[nums.length];
int sum = 1;
int tark = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0){
tark++;
continue;
}
sum *= nums[i];
}
if(tark == 0){
for(int j = 0;j < nums.length; j++){
output[j] = sum / nums[j];
}
}
else if(tark == 1){
for(int i = 0;i < nums.length; i++){
if(nums[i] == 0){
output[i] = sum;
continue;
}
output[i] = 0;
}
}
else{
for(int j = 0;j < nums.length; j++){
output[j] = 0;
}
}
return output;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.