diff options
author | Jack Sangdahl <[email protected]> | 2025-07-30 20:38:10 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-30 20:38:10 -0600 |
commit | 432f582bd1d66c3b87fd365846a620d4a4d9f8a8 (patch) | |
tree | 0f44c09d0555ecc84131f5db55e1a7e39f59e9a9 | |
parent | 64ccda3aff7e186e03bdc963a8ab110d2bc01e19 (diff) | |
download | leetcode-432f582bd1d66c3b87fd365846a620d4a4d9f8a8.tar.gz leetcode-432f582bd1d66c3b87fd365846a620d4a4d9f8a8.zip |
898. bitwise ors of subarrays
-rw-r--r-- | bitwise_or_subarray.c | 88 | ||||
-rw-r--r-- | bitwise_or_subarray.py | 29 |
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])) |