C++ | Detailed Explanation with Proofs |
Intuition\n Describe your first thoughts on how to solve this problem. \nNot much intuitive as it does not invole any famous algorithm but a bit of observation.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNot much intuitive as it does not invole any famous algorithm but a bit of observation.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- First and the only thing to notice is that if we have to divide the array into three parts with equal value then ***each part must have equal number of 1 in them.***\nTake your time :) \nProof->\nAs each number must have equal value which means in binary form (After removing leading zeros ) each of them must be equivalent in the position of their bits.\nAnd for all of them to be equivalent , the sufficient condition will be for them to have the equal number of set bits \'1\' in them, we can\'t take zeros \'0\' as it can form leading zeros which will then become unsignificant.\n\n- So calculate the total number of ones and check for it to be a multiple of three. There will be a special case for 0 number of ones ( See the code for it ).\nIf it\'s a multiple of three then, again traverse the array to get the starting point of all the individual parts as\n**First part -> first \'1\' index\nsecond part -> total_one/3+1 th \'1\' index\nthird part -> total_one/3 + total_one/3 + 1 th \'1\' index.**\n\n- Now we have our starting indexes we just have to check if we could actually make them equivalent and for that we simply traverse in our third part till last and correspondingly check the indices in first part and second part.\nIf we reach the end of array ,which means we have the corresponding indices of each part equal, so we could actually divide them and the remaining values will serve as leading zeros for individual parts.\n\n***See the code for more details or try to dry run on any test case for better understanding.***\n \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ Traversing the array three times.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> threeEqualParts(vector<int>& arr) {\n        int n=arr.size(),ones=count(arr.begin(),arr.end(),1);\n        if(ones==0) return {0,n-1}; // if full array is of zeros\n        if(ones%3) return {-1,-1};\n\n        ones=ones/3; // calculating the size of each block with equal ones.\n\n\n        int curr_one=0,first=-1,second=-1,third=-1;\n        for(int i=0;i<n;i++) {\n            if(arr[i]==1) curr_one++;\n\n            if(curr_one==1 and first==-1) first=i;\n            else if(curr_one==ones+1 and second==-1) second=i;\n            else if(curr_one==2*ones+1 and third==-1) third=i;\n        }\n\n        int i,j,k;\n        for(i=first,j=second,k=third;k<n;i++,j++,k++) {\n            if(not (arr[i]==arr[j] and arr[j]==arr[k])) return {-1,-1};\n        }\n        return {i-1,j};\n    }\n};\n```
['Array', 'Math', 'C++']