Jump to content

  • Log In with Google      Sign In   
  • Create Account

Understanding an algorithm solution


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 AhmedCoeia   Members   -  Reputation: 352

Like
0Likes
Like

Posted 10 December 2012 - 11:00 PM

I wanted to solve the problem here on my own: To find the longest substring with equal sum in left and right in C++ http://stackoverflow.com/questions/8469407/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)&amp;&amp;(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.

Edited by AhmedCoeia, 10 December 2012 - 11:12 PM.


Sponsor:

#2 Cornstalks   Crossbones+   -  Reputation: 6995

Like
0Likes
Like

Posted 10 December 2012 - 11:06 PM

Please use [ code ][ /code ] (without spaces) tags (to get pretty formatted code)! I'll recreate it here in the meantime:

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'd help analyze it but I've got to study for some finals Posted Image
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#3 AhmedCoeia   Members   -  Reputation: 352

Like
0Likes
Like

Posted 10 December 2012 - 11:13 PM

I just need the part with int temp = i+j-1. How it was done by picture or by some examples...

#4 wqking   Members   -  Reputation: 756

Like
0Likes
Like

Posted 10 December 2012 - 11:53 PM

Why did you mention temp = i + j - 1 two times?
It is temp = j - i + 1, which is the character count between index i and j.
The algorithm is extract every sub string and compare the sum at even and odd indexes.

http://www.cpgf.org/
cpgf library -- free C++ open source library for reflection, serialization, script binding, callbacks, and meta data for OpenGL Box2D, SFML and Irrlicht.
v1.5.5 was released. Now supports tween and timeline for ease animation.


#5 AhmedCoeia   Members   -  Reputation: 352

Like
0Likes
Like

Posted 11 December 2012 - 03:52 AM

I don't know how the calculation is done to say temp = j-i+1. I can't visualize it.

#6 Zao   Members   -  Reputation: 882

Like
1Likes
Like

Posted 11 December 2012 - 05:11 PM

Let's state in plain text what the outer shell of the algorithm does:
For each offset i in the string - take successively larger substrings of even length from that offset, until the end of the string is reached.
i is the left index of the substring, inclusive.
j is the right index of the substring, inclusive. j+1 is the right index of the string, exclusive

We cannot immediately use j in our expressions, as we want to both find out if a substring is even and the substring(off,n) function takes an absolute count n of characters.

We can set up an equation to find the length from i and j, looking for "what number must we add to i to get the index of one character to the right of j":
i + len = j + 1
len = j + 1 - i
len = j - 1 + 1
To make it is hell. To fail is divine.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS