aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-30 20:38:10 -0600
committerJack Sangdahl <[email protected]>2025-07-30 20:38:10 -0600
commit432f582bd1d66c3b87fd365846a620d4a4d9f8a8 (patch)
tree0f44c09d0555ecc84131f5db55e1a7e39f59e9a9
parent64ccda3aff7e186e03bdc963a8ab110d2bc01e19 (diff)
downloadleetcode-432f582bd1d66c3b87fd365846a620d4a4d9f8a8.tar.gz
leetcode-432f582bd1d66c3b87fd365846a620d4a4d9f8a8.zip
898. bitwise ors of subarrays
-rw-r--r--bitwise_or_subarray.c88
-rw-r--r--bitwise_or_subarray.py29
2 files changed, 117 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
+}
diff --git a/bitwise_or_subarray.py b/bitwise_or_subarray.py
new file mode 100644
index 0000000..9c15024
--- /dev/null
+++ b/bitwise_or_subarray.py
@@ -0,0 +1,29 @@
+# 898. Bitwise ORs of Subarrays
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def subarrayBitwiseORs(self, arr):
+ """
+ :type arr: List[int]
+ :rtype: int
+ """
+ ans, curr = set(), set()
+ for i in arr:
+ curr = {i | j for j in curr} | {i}
+ ans |= curr
+ return len(ans)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.subarrayBitwiseORs(arr=[0]))
+ print(obj.subarrayBitwiseORs(arr=[1, 1, 2]))
+ print(obj.subarrayBitwiseORs(arr=[1, 2, 4]))