Beats 100% time and space || O(n) Java Solution || Bits manipulation || In-depth Explanation
Intuition\nIt looked like dp problem to me so I couldn\'t went in depth of bits during the contest and wasn\'t able to do this in contest cause conversion of gr
# Intuition\nIt looked like dp problem to me so I couldn\'t went in depth of bits during the contest and wasn\'t able to do this in contest cause conversion of greedy recursion to dp was hard task. This problem is completely based on understanding of bits behaviour under the constraint of given problem\n\n# Approach\n=> **we check total array AND value and if its greater then 0. Then we return 1**\nREASON: if total And is greater than 0. Its means its positive number which have some bits set.\nWhich also means, all the element of the array have those bit set. So any partition we make, all partition will have those bits set for sure. Therefore sum of partitions will be sure greater than equal to noOfPartiton*totalAnd.\nSo having one complete partition is the only way of getting less score. Any other partiton will increases the score.\n\n**=> totalAnd is 0.**\nhere totalAns is 0. so least score we can make is 0 only.\nnow we need to check all partiton having score 0 to increase the no.of partition while mainting the score of each partition 0. so that the total score shouldn\'t increase more than 0.\n\nwe traverse left to right we check all the partiton who have score 0. and inrease our partition count.\nnow lets say, we have made 3 partition after the loop is done. having come till 3rd partition bydefault says that we have found 2 partition whose score are 0. But there can be 2 possibilty for 3rd or last partition. \n1st possibilty => last partition score is 0. in this case we return count which is 3\n\t2ND POSSIBILITY = > last partion score is not 0. so what we do is merge last partition with 2nd last partition because 2nd last partition have score 0 and we do AND operation. so 0 AND lastpartition score is also 0.\n\tAnd by merging last 2 partition we have kept the score of all partition 0. and also created max number of partition we can make. so we just do count--, to reduce the partition count. and return it.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\n    public int maxSubarrays(int[] nums) {\n        int totalAnd = nums[0];\n        int n = nums.length;\n        for(int num:nums){\n            totalAnd = totalAnd & num;\n        }\n        if(totalAnd>0){\n            return 1;\n        }\n        int currAnd = 0;\n        int split = 0;\n        for(int i=0;i<n;i++){\n            if(currAnd==0){\n                currAnd = nums[i];\n                split++;\n            }else {\n                currAnd = currAnd & nums[i];\n            }\n        }\n        if(currAnd>0){\n            split--;\n        }\n        return split;\n    }   \n}\n```
['Array', 'Bit Manipulation', 'Java']