[C++] Double to Single-Pass with BitMask, 68ms, 104.78MB
The problem is basically ask us to group consecutive elements so that the score is the lowest possible and since we are using a & operator, we know that this lo
The problem is basically ask us to group consecutive elements so that the score is the lowest possible and since we are using a `&` operator, we know that this lowest value can only go down as we add more values.\n\nAnd this is a key factor, since it means that our lowest possible score can\'t be lower or higher than the one we get by `&`ing all the elements together: it has to be it, since otherwise:\n* we might get a greater or equal score from a group adding more elements;\n* we cannot go below the cumulative `&` value by adding more.\n\nWith this in mind, we might then simply group using another pass to find all the elements that we can group together.\n\nFor example for the first case we will have the overall `&`ed value of `0` and we can find `3` groups that go up to that, as explained: `{1,0}`, `{2,0}` and `{1,2}`.\n\nThe situation is slightly complicated when we figure out that any cumulative value `> 1` actually means that we are better off just merging the groups instead of having more than one of them adding up to the score.\n\nWith that in mind, we can proceed with our logic, starting by our usual support variables:\n* `res` will store how many groups we can create;\n* `len` will store the length of our input;\n* `curr` will store the current `&` product, initially set to `INT_MAX` (to make sure we have all the bits of a positive number in range set to `1` - it is basically the neuter element of our process);\n* `minBit` will store the cumulative value of all the `&`ed values.\n\nWe can then rule out the case where `minBit > 0`, since in that case, as stated before, we are better off just grouping all the elements in one - no point in having any `minBit + minBit + minBit + ...` overall series of groups certainly scoring `> minBit`, so in this case we can just `return` `1`.\n\nNow, when `minBit` is actually `0`, we can proceed with a greedy approach to forming our groups, so that for each value `n` in `nums` we will:\n* `&` `n` in `curr`;\n* check if `curr` now equals `minBit` (ie: `0`) and if so, we can start a group by splitting and:\n    * increase `res` by `1`;\n    * reset `curr` to be `INT_MAX`.\n\nOnce done, we can `return` `res`.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int maxSubarrays(vector<int>& nums) {\n        // support variables\n        int res = 0, len = nums.size(), curr = INT_MAX,\n            minBit = accumulate(begin(nums), end(nums), INT_MAX, bit_and<int>());\n        // minBit is too expensive\n        if (minBit > 1) return 1;\n        // parsing nums\n        for (int n: nums) {\n            curr &= n;\n            // if we reached the target minBit, we try to open a new sub array\n            if (curr == minBit) {\n                res++;\n                curr = INT_MAX;\n            }\n        }\n        return res;\n    }\n};\n```\n\nBut, wait a moment: since we know that the only case in which we can split groups is when our current bitwise `&` product is `0`, we can skip one passage (the `accumulate` one) and go directly with a single one where we will count how often do we get `0`s (if we can get it even a single time, then the minimum score has to be `0`) and finally `return` `res` if it is `> 0` (ie: we encountered at least a `0` product), `1` otherwise.\n\n```cpp\nclass Solution {\npublic:\n    int maxSubarrays(vector<int>& nums) {\n        // support variables\n        int res = 0, curr = INT_MAX;\n        // parsing nums\n        for (int n: nums) {\n            curr &= n;\n            // if we reached a cumulative 0, we try to open a new sub array\n            if (!curr) {\n                res++;\n                curr = INT_MAX;\n            }\n        }\n        return res ? res : 1;\n    }\n};\n```
['Array', 'Bit Manipulation', 'Bitmask', 'C++']