aboutsummaryrefslogtreecommitdiff
path: root/bitwise_or_subarray.c
diff options
context:
space:
mode:
Diffstat (limited to 'bitwise_or_subarray.c')
-rw-r--r--bitwise_or_subarray.c88
1 files changed, 88 insertions, 0 deletions
diff --git a/bitwise_or_subarray.c b/bitwise_or_subarray.c
new file mode 100644
index 0000000..bfda6dc
--- /dev/null
+++ b/bitwise_or_subarray.c
@@ -0,0 +1,88 @@
+// 898. Bitwise ORs of Subarrays
+#include "leetcode.h"
+
+/*
+ * given an integer array 'arr', return the number of distinct bitwise or's of
+ * all the non-empty subarrays of 'arr'. the bitwise or of a subarray is the
+ * bitwise or of each interger in the subarray. the bitwise or of a subarray of
+ * one integer is that integer. a subarray is a contiguous non-empty sequence of
+ * elements within an array.
+ */
+
+struct node {
+ int value;
+ struct node *next;
+};
+
+struct hashset {
+ struct node **buckets;
+ int size;
+ int capacity;
+};
+
+struct hashset *hashset_create(int capacity) {
+ struct hashset *obj = (struct hashset *)malloc(sizeof(struct hashset));
+ obj->buckets = (struct node **)calloc(capacity, sizeof(struct node *));
+ obj->size = 0;
+ obj->capacity = capacity;
+ return obj;
+}
+
+bool contains(struct hashset *set, int value) {
+ uint hash = (uint)value % set->capacity;
+ struct node *curr = set->buckets[hash];
+ while (curr) {
+ if (curr->value == value)
+ return true;
+ curr = curr->next;
+ }
+ return false;
+}
+
+void insert(struct hashset *set, int value) {
+ if (contains(set, value))
+ return;
+ uint hash = (uint)value % set->capacity;
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->value = value;
+ new->next = set->buckets[hash];
+ set->buckets[hash] = new;
+ set->size++;
+}
+
+void hashset_free(struct hashset *obj) {
+ for (int i = 0; i < obj->capacity; i++) {
+ struct node *curr = obj->buckets[i];
+ while (curr) {
+ struct node *tmp = curr;
+ curr = curr->next;
+ free(tmp);
+ }
+ }
+ free(obj->buckets);
+ free(obj);
+}
+
+int subarrayBitwiseORs(int *arr, int arrSize) {
+ struct hashset *set = hashset_create(1024);
+ for (int i = 0; i < arrSize; i++) {
+ int j = i - 1, x = 0, y = arr[i];
+ insert(set, y);
+ while (j >= 0 && x != y) {
+ x |= arr[j];
+ y |= arr[j];
+ insert(set, y);
+ j--;
+ }
+ }
+ int ans = set->size;
+ hashset_free(set);
+ return ans;
+}
+
+int main() {
+ int a1[] = {0}, a2[] = {1, 1, 2}, a3[] = {1, 2, 4};
+ printf("%d\n", subarrayBitwiseORs(a1, ARRAY_SIZE(a1))); // expect: 1
+ printf("%d\n", subarrayBitwiseORs(a2, ARRAY_SIZE(a2))); // expect: 3
+ printf("%d\n", subarrayBitwiseORs(a3, ARRAY_SIZE(a3))); // expect: 6
+}