CODEWITHSUNDEEP
c++algorithm
Andre
Andre

Reputation: 43

Understanding an algorithm solution

I wanted to solve the problem here on my own: To find the longest substring with equal sum in left and right in C++

The code is here

int getEqualSumSubstring(string s) {
    int i=0,j=i,foundLength=0;
    for(i=0;i<s.length();i++)
    {
        for(j=i;j<s.length();j++)
        {
            int temp = j-i+1;

            if(temp%2==0)
            {
                int leftSum=0,rightSum=0;
                string tempString=s.substr(i,temp);
                // printf("%d ",tempString.length());
                for(int k=0;k<temp/2;k++)
                {
                    leftSum=leftSum+tempString[k]-48;
                    rightSum=rightSum+tempString[k+(temp/2)]-48;
                }
                if((leftSum==rightSum)&&(leftSum!=0))
                    if(tempString.length()>foundLength)
                    foundLength=tempString.length(); 
            }
        }
    }
    return(foundLength);
}

I wanted to know how the calculation of temp = i+j-1 is done ? how on paper or by examples he could get that equation. I tried a lot but I couldn't get it.

Upvotes: 0

Views: 116

Answers (1)

Victor
Victor

Reputation: 428

It is just the length of the substring, where i and j are left and right bounds of the substring respectively. If we have a segment on the line from x to y, x < y, then it's length is y - x. As we have here a discrete object, the length can vary by 1 or 2. Here, as we took closed bounds, the length of the substring both starting and ending in the position i will be 1 = i - i + 1, so the formula should be j - i + 1.

Upvotes: 1

Related Questions