aboutsummaryrefslogtreecommitdiff
path: root/subarr_product_less_k.c
diff options
context:
space:
mode:
Diffstat (limited to 'subarr_product_less_k.c')
-rw-r--r--subarr_product_less_k.c46
1 files changed, 46 insertions, 0 deletions
diff --git a/subarr_product_less_k.c b/subarr_product_less_k.c
new file mode 100644
index 0000000..c8227e0
--- /dev/null
+++ b/subarr_product_less_k.c
@@ -0,0 +1,46 @@
+// 713. Subarray Product Less Than K
+#include "leetcode.h"
+
+/*
+ * given an array of integers 'nums' and an integer 'k', return the number of
+ * contiguous subarrays where the product of all the elements in the subarray is
+ * strictly less than 'k'.
+ */
+
+int numSubarrayProductLessThanK(int *nums, int numsSize, int k) {
+ int n = numsSize, ans = 0, prod = 0, line = 0;
+ for (int i = 0; i < n; i++) {
+ for (int j = i; j < n; j++) {
+ if (i == j) {
+ prod = nums[i];
+ if (prod < k) {
+ line++;
+ continue;
+ } else
+ break;
+ } else {
+ prod *= nums[j];
+ if (prod < k)
+ line++;
+ else
+ break;
+ ;
+ }
+ }
+ if (line == n - i)
+ break;
+ else
+ ans += line;
+ }
+ for (int i = line; i >= 0; i--)
+ ans += i;
+ return ans;
+}
+
+int main() {
+ int n1[] = {10, 5, 2, 6}, n2[] = {1, 2, 3};
+ printf("%d\n",
+ numSubarrayProductLessThanK(n1, ARRAY_SIZE(n1), 100)); // expect: 8
+ printf("%d\n",
+ numSubarrayProductLessThanK(n2, ARRAY_SIZE(n2), 0)); // expect: 0
+}