om1429888's blog

By om1429888, history, 6 weeks ago,

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.

• 0

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by om1429888 (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 https://pastebin.com/gZ8N01nR My solution.
•  » » 6 weeks ago, # ^ |   0 thanks bro!can u pls tell the logic behind upperbound?