aboutsummaryrefslogtreecommitdiff
path: root/product_array_except_self.c
blob: 3a125da88fd4c483fe9236cf9c38f4fe20540d86 (plain)
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
// 238. Product of Array Except Self
#include "leetcode.h"

/*
 * given an integer array 'nums' return an array 'answer' such that 'answer[i]'
 * is equal to the product of all the elements of 'nums' except 'nums[i]'. the
 * product of any prefix or suffix of 'nums' is guaranteed to fit in a 32-bit
 * integer. you must write an algorithm that runs in O(n) time and without the
 * division operation.
 */

int *productExceptSelf(int *nums, int nums_size, int *return_size) {
  int *ans = (int *)malloc(nums_size * sizeof(int));
  *return_size = nums_size;
  ans[0] = 1;
  for (int i = 1; i < nums_size; i++)
    ans[i] = nums[i - 1] * ans[i - 1];
  int tmp = 1;
  for (int i = nums_size - 1; i >= 0; i--) {
    ans[i] *= tmp;
    tmp *= nums[i];
  }
  return ans;
}

int main() {
  int n1[] = {1, 2, 3, 4}, n2[] = {-1, 1, 0, -3, 3};
  int rs1[] = {}, rs2[] = {};
  int *pes1 = productExceptSelf(n1, ARRAY_SIZE(n1), rs1);
  int *pes2 = productExceptSelf(n2, ARRAY_SIZE(n2), rs2);
  for (int i = 0; i < ARRAY_SIZE(n1); i++)
    printf("%d ", pes1[i]); // expect: 24 12 8 6
  printf("\n");
  for (int i = 0; i < ARRAY_SIZE(n2); i++)
    printf("%d ", pes2[i]); // expect: 0 0 9 0 0
  printf("\n");
}