Sum of all the submatrices approach #2 O(n^4)

#1

Please check why the sum is coming out to be one less than the correct answer.

Please help me correct the loop- Prefix Array Sum
#2

you have not applied conditions correctly
correct way is

   for(int li=0; li<n; li++){
        for(int lj=0; lj<n; lj++){
            for(int bi=li; bi<n; bi++ ){
                for(int bj=lj; bj<n; bj++){
                    int temp=arr[bi][bj];
                    if(lj>0)temp-=arr[bi][lj-1];
                    if(li>0)temp-=arr[li-1][bj];
                    if(li>0&&lj>0)temp+=arr[li-1][lj-1];
                    // cout<<temp<<"\n";
                    sum+=temp;
                }
            }
        }
    }

this will give correct output

#3

Hey can you point out what was the problem with my code?

#4

in line 54 to 56

				else if(li==0){
					sum+=arr[bi][bj]-arr[bj][lj-1];
				}

this should be

				else if(li==0){
					sum+=arr[bi][bj]-arr[bi][lj-1];
				}

i hope your doubt is resolved
if you have no further query regarding this
please mark it as resolved

1 Like
#5

Thank you! :smile: Do you know how to mark it as resolved? I can’t seem to find any previous doubts in ask doubt section.

#6

@rachitbansal2500
in course page in library tab there is a doubts section where all doubts are shown.