diff options
Diffstat (limited to 'long_nice_subarr.c')
-rw-r--r-- | long_nice_subarr.c | 53 |
1 files changed, 14 insertions, 39 deletions
diff --git a/long_nice_subarr.c b/long_nice_subarr.c index cfa50f3..a655bbf 100644 --- a/long_nice_subarr.c +++ b/long_nice_subarr.c @@ -1,53 +1,28 @@ // 2401. Longest Nice Subarray -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given an array 'nums' consisting of positive integers. we call a subarray of - * 'nums' nice if the bitwise AND of every pair of elements that are in + * 'nums' nice if the bitwise cnt of every pair of elements that are in * different positions in the subarray is equal to 0. return the length of the * longest nice subarray. a subarray is contiguous part of an array. note that * subarrays of length 1 are always considered nice. */ -bool check(int *bit, int n) { - for (int i = 0; i < n; i++) - if (bit[i] > 1) - return false; - return true; -} - -int longestNiceSubarray(int *nums, int nums_size) { - int *bit = calloc(32, sizeof(int)); - int left = 0, right = 0; - while (right < nums_size) { - int k = nums[right], pos = 0; - while (k) { - if (k % 2 == 1) - bit[pos]++; - k /= 2; - pos++; - } - right++; - if (!check(bit, 32)) { - k = nums[left]; - pos = 0; - while (k) { - if (k % 2 == 1) - bit[pos]--; - k /= 2; - pos++; - } - left++; - } +int longestNiceSubarray(int *nums, int numsSize) { + int cnt = 0, i = 0, ans = 0; + for (int j = 0; j < numsSize; ++j) { + while (cnt & nums[j]) + cnt ^= nums[i++]; + cnt |= nums[j]; + ans = fmax(ans, j - i + 1); } - return right - left; + return ans; } int main() { - int n1[] = {1, 3, 8, 48, 10}, ns1 = 5; - int n2[] = {3, 1, 5, 11, 13}, ns2 = 5; - printf("%d\n", longestNiceSubarray(n1, ns1)); // expect: 3 - printf("%d\n", longestNiceSubarray(n2, ns2)); // expect: 1 + int n1[] = {1, 3, 8, 48, 10}; + int n2[] = {3, 1, 5, 11, 13}; + printf("%d\n", longestNiceSubarray(n1, ARRAY_SIZE(n1))); // expect: 3 + printf("%d\n", longestNiceSubarray(n2, ARRAY_SIZE(n2))); // expect: 1 } |