om1429888's blog

By om1429888, history, 6 weeks ago, In English

https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/

THIS IS THE QUESTION.

THIS IS MY SOLUTION.

class Solution {
public:
    long long mod=1000000000+7;
    int waysToSplit(vector<int>& nums) {
    vector<long long>v(nums.size(),0);
    v[0]=nums[0];
    for(int i=1;i<nums.size();i++){
        v[i]=v[i-1]+nums[i];
    }
    int j=0;
    long long count=0;
    for(int i=0;i<nums.size()-2;i++){
        if(j==i)j++;
        while(j<nums.size()-1&&v[i]>v[j]-v[i])j++;
        if(j==nums.size()-1||v[nums.size()-1]-v[j]<v[j]-v[i])break;
        int start=j+1;
        int end=nums.size()-1;
        while(start<=end){
            int mid=start+(end-start)/2;
            if(v[mid]-v[i]>v[nums.size()-1]-v[mid])end=mid-1;
            else start=mid+1;
        }
        count+=end-j+1;
        count%=mod;
    }
    return count%mod;
    }
};

for the left part im iterating using 'i'and 'j' signfies the middle part, for the last right part im using binary search to find the last index j can go and calculating it in count.it is giving one less than answer for the following test case: [8892,2631,7212,1188,6580,1690,5950,7425,8787,4361,9849,4063,9496,9140,9986,1058,2734,6961,8855,2567,7683,4770,40,850,72,2285,9328,6794,8632,9163,3928,6962,6545,6920,926,8885,1570,4454,6876,7447,8264,3123,2980,7276,470,8736,3153,3924,3129,7136,1739,1354,661,1309,6231,9890,58,4623,3555,3100,3437] It should be 227,my code is returning 226. Please Help,Thanks.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by om1429888 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks bro!can u pls tell the logic behind upperbound?