Prefix counting AND result zero - Java T:O(N) S:O(1)
Intuition\n Describe your first thoughts on how to solve this problem. \nOthers explain very well on why this is counting AND zero in prefix. Here just to add t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nOthers explain very well on why this is counting AND zero in prefix. Here just to add the point why we can increase the zero count by `1` as soon as we detect the AND result is zero in prefix and restart the accumlation.\n\nWhen accumlate AND current `==0`, we detect a subarray in prefix that produces `0`, it could be statndalone `0` or end by `0` (`40`) or no `0` (`12`), in all cases, they are as good as a standalone `0`. We can  [**opt1**] put it as a separate subarray; or [**opt2**] expand it to the right into a bigger array to achieve the smallest subarray requirement.\n\nIn **opt1**, we need to make sure the next subarray is also AND result zero, otherwise it violate the requirement and it becomes the case of **opt2**. Now we see that we can safely incrase zero count and start checking the right, if the right subarray is zero, the count will increase again, if not, it is the **op2** and the zero count is good. The take away is in either case of **op1** and **opt2**, we can increse the zero count as soon as we detect AND zero.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int maxSubarrays(int[] nums) {\n        // couting AND zeros in prefix\n        int carry = -1, sum = 0;\n        for (int val : nums) {\n            if ((carry = carry & val) == 0) {\n                // zero detected\n                sum++;\n                carry = -1;\n            }\n        }\n        return Integer.max(1, sum);\n    }\n}\n```
['Java']