codekofi
← All questions

Product of Array Except Self

HardArrays & Hashing

The problem

Given an integer array, return an array where each element is the product of every other element.

Solve it without using division, in linear time.

productExceptSelf({1, 2, 3, 4})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1vector<int> productExceptSelf(const vector<int>& nums) {
2
3 int n = nums.size();
4 vector<int> ans(n, 1);
5
6 int running = 1;
7
8 for (int i = 0; i < n; i++) {
9 ans[i] = running;
10 running = running * nums[i];
11 }
12
13 running = 1;
14
15 for (int i = n - 1; i >= 0; i--) {
16 ans[i] = ans[i] * running;
17 running = running * nums[i];
18 }
19
20 return ans;
21}
1vector<int> productExceptSelf(const vector<int>& nums) {
2
3 int n = nums.size();
4 vector<int> ans(n, 1);
5
6 int running = 0;
7
8 for (int i = 0; i < n; i++) {
9 running = running * nums[i];
10 }
11
12 running = 1;
13
14 for (int i = n - 1; i >= 0; i--) {
15 ans[i] = ans[i] * running;
16 running = running * nums[i];
17 }
18
19 return ans;
20}
1vector<int> productExceptSelf(const vector<int>& nums) {
2
3 int n = nums.size();
4 vector<int> ans(n, 1);
5
6 int running = 0;
7
8 for (int i = 0; i < n; i++) {
9 ans[i] = running;
10 running = running * nums[i];
11 }
12
13 running = 0;
14
15 for (int i = n - 1; i >= 0; i--) {
16 ans[i] = ans[i] * running;
17 running = running * nums[i];
18 }
19
20 return ans;
21}