-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathProduct of Array Except Self.java
More file actions
48 lines (38 loc) · 1.69 KB
/
Product of Array Except Self.java
File metadata and controls
48 lines (38 loc) · 1.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public int[] productExceptSelf(int[] nums) {
//array to store the result
int[] answer = new int[nums.length];
//array to store the prefix product of nums array
int[] prefixProduct = new int[nums.length];
//array to store the suffixproduct of nums array
int[] suffixProduct = new int[nums.length];
//initialize the prefix product
prefixProduct[0] = 1;
//calculate the prefix product
for(int i=1; i<prefixProduct.length; i++)
prefixProduct[i] = prefixProduct[i-1] * nums[i-1];
//reverse the nums array to calculate the suffix prodcut as a prefix product for the reversed nums array
reverse(nums, nums.length);
//initialize the suffix product
suffixProduct[0] = 1;
//calculate the prefix product for the reversed array(suffix product for the nums array before reversed)
for(int i=1; i<suffixProduct.length; i++)
suffixProduct[i] = suffixProduct[i-1] * nums[i-1];
//calculate product of for each element except its self by multiplying the prefix and suffix product
for(int i=0; i<answer.length; i++)
//the suffix product is reversed so we should start from the end
answer[i] = prefixProduct[i] * suffixProduct[(answer.length - 1) - i];
//return the result
return answer;
}
//function to reverse an array
public void reverse(int a[], int n)
{
int i, k, t;
for (i = 0; i < n / 2; i++) {
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
}