diff options
-rw-r--r-- | long_nice_subarr.c | 53 | ||||
-rw-r--r-- | long_nice_subarr.py | 31 |
2 files changed, 45 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 } diff --git a/long_nice_subarr.py b/long_nice_subarr.py new file mode 100644 index 0000000..037743e --- /dev/null +++ b/long_nice_subarr.py @@ -0,0 +1,31 @@ +# 2401. Longest Nice Subarray + +""" +given an array 'nums' consisting of positive integers. we call a subarray of +'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. +""" + + +class Solution(object): + def longestNiceSubarray(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + cnt, i, ans = 0, 0, 0 + for j in range(len(nums)): + while cnt & nums[j]: + cnt ^= nums[i] + i += 1 + cnt |= nums[j] + ans = max(ans, j - i + 1) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestNiceSubarray(nums=[1, 3, 8, 48, 10])) + print(obj.longestNiceSubarray(nums=[3, 1, 5, 11, 13])) |