C++ || BINARY SEARCH || Prefix Sum
\n\n\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) \n    {\n        long long count=0,M=1000000007;\n        int n=nums.size();\n        \n
\n![image.png](https://assets.leetcode.com/users/images/188cf10b-e4a5-4cd2-970b-64a17c0fc709_1687511283.4797945.png)\n```\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) \n    {\n        long long count=0,M=1000000007;\n        int n=nums.size();\n        \n        vector<long long int> prefix(n,nums[0]);\n        for(int i=1;i<n;i++)\n        prefix[i]=prefix[i-1]+nums[i];\n        // we have calculated the prefix sum for finding sum of lrm in O(1) time.\n        \n        for(int i=0;i<n-1;i++)\n        {   \n            int right=-1,left=-1; // for storing the indexes;\n            \n            int lo=i+1,hi=n-2;\n            //we calculate the right-most valid index\n            while(lo<=hi)\n            {\n                int mid=lo+(hi-lo)/2;\n                if(prefix[mid]-prefix[i]<=prefix.back()-prefix[mid])\n                {\n                    right=mid;\n                    lo=mid+1;\n                }\n                else\n                    hi=mid-1;\n            }\n            \n            lo=i+1;hi=n-2;\n            //we calculate the left-most valid index\n             while(lo<=hi)\n            {\n                int mid=lo+(hi-lo)/2;\n                if(prefix[i]<=prefix[mid]-prefix[i])\n                {\n                    left=mid;\n                    hi=mid-1;\n                }\n                else\n                    lo=mid+1;\n            }\n            //invalid condition check i.e. if one of the bound does not exist \n            //or left bound is greater than right bound\n            if(left==-1||right==-1||left>right)continue;\n            \n            count=(count+(right-left+1)%M)%M;\n        }\n        return count;\n    }\n};\n```\n# Sol 2 with lowerbound and upperbound :\n```\nclass Solution {\npublic:\n    int mod = 1e9+7;\n    \n    int waysToSplit(vector<int>& nums) \n    {\n        int i, left, remaining, mid_startpoint, mid_endpoint, max_mid, length, n = nums.size();\n\n        vector<int>sum(n, 0);\n        sum[0] = nums[0];\n        for(i = 1; i < n; i++) \n            sum [i] = sum[i-1] + nums[i];\n        \n        long long ans=0;\n        for(i = 0; i < n; i++) \n        {\n            left = sum[i];\n            remaining = sum[n-1] - left;\n\n            max_mid = remaining/2;\n                 \n            mid_startpoint = lower_bound(sum.begin() + i + 1, sum.end(), sum[i] + left) - sum.begin();\n            \n            // have to apply search upto n-1 otherwise an empty right part will also be counted\n            mid_endpoint = upper_bound(sum.begin() + i + 1, sum.begin() + n - 1  , sum[i] + max_mid) - sum.begin();\n            mid_endpoint--;\n\n            length = (mid_endpoint - mid_startpoint + 1);\n            \n            ans += max(0, length);\n        }\n        \n        return ans % mod;\n    }\n}; \n
['Binary Search', 'C', 'Prefix Sum']