Split Array Into Maximum Number Of Subarrays, C++ Explained Solution
Upvote If Found Helpful !!!\n\n# Approach\n Describe your approach to solving the problem. \nThe problem here is quite simple and needs some simple observations
**Upvote If Found Helpful !!!**\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem here is quite simple and needs some simple observations from Bit Manipulation. First of all, its important to divide problem into two cases : If bitwise **AND** of complete array is **zero** or it is **non-zero**. In case, if bitwise **AND** is non-zero, the only answer possible is the complete array itself or answer is always **1** in such case. But why ? If bitwise AND of complete array is non-zero, then it means that some bits are set in all numbers. Lets say that some bit **k** is set in all **N** numbers. If we divide array into **M** subarrays, then contribution of this bit in sum will occur **M** times while taking whole array, its contribution is limited to only a single time, thus its better to take complete array as we need to minimise sum. \n\nNow for second case when bitwise AND of array is **zero**. In this case we just need to check whenever AND becomes 0, increment count by 1. Implementation goes below : \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 {\npublic:\n    int maxSubarrays(vector<int>& nums) {\n        ios_base::sync_with_stdio(0);\n        int n = nums.size(),val = nums[0];\n        for(int i = 1; i < n; i++){\n            val &= nums[i];\n        }\n        if(val > 0){\n            return 1;\n        }\n        else{\n            int ans = 0;\n            for(int i = 0; i < n;){\n                int k = nums[i];\n                if(k == 0){\n                    ans++;\n                    i++;\n                    continue;\n                }\n                while(i < n && k > 0){\n                    k &= nums[i];\n                    i++;\n                }\n                if(k == 0){\n                    ans++;\n                }\n            }\n            return ans;\n        }\n    }\n};\n```
['Array', 'Math', 'Bit Manipulation', 'C++']