## Longest Contiguous Equal Sum Substring of length 2N

## Interview Question (April 2012)

**Problem Statement**Complete the function getEqualSumSubstring, which takes a single argument.

The single argument is a string s, which contains only non-zero digits.

This function should print the length of longest contiguous substring of s,

such that the length of the substring is 2*N digits and the sum of the

leftmost N digits is equal to the sum of the rightmost N digits.If there

is no such string, your function should print 0. Sample Test Cases: Input #00: 123231 Output #00: 6 Explanation: 1 + 2 + 3 = 2 + 3 + 1. The length of the longest substring = 6 where the sum of 1st half = 2nd half Input #01: 986561517416921217551395112859219257312 Output #01: 36

**Solution**
int getEqualSumSubString(char s[], int n)

{

int sum[N];

sum[0]=s[0];

for(int i=1;i<N;i++)

{

sum[i]=sum[i-1]+s[i];

}

int max=0;

int si=0;

for(int i=1;i<N;i++)

{

for(int j=0;j<i;j++)

{

if((i-j+1)%2==0)

{

int left;

if(j==0)

left=sum[(i-j+1)/2+j-1];

else

left=sum[(i-j+1)/2+j-1]-sum[j-1];

int right=sum[i]-sum[(i-j+1)/2+j-1];

if(left==right)

{

if((i-j+1)>max)

max=(i-j+1);

}

}

}

}

return max;

}

int sum[N];

sum[0]=s[0];

for(int i=1;i<N;i++)

{

sum[i]=sum[i-1]+s[i];

}

int max=0;

int si=0;

for(int i=1;i<N;i++)

{

for(int j=0;j<i;j++)

{

if((i-j+1)%2==0)

{

int left;

if(j==0)

left=sum[(i-j+1)/2+j-1];

else

left=sum[(i-j+1)/2+j-1]-sum[j-1];

int right=sum[i]-sum[(i-j+1)/2+j-1];

if(left==right)

{

if((i-j+1)>max)

max=(i-j+1);

}

}

}

}

return max;

}

__O(n2)__

**Time Complexity:**// If you find this blog somewhat helpful, please share it and Keep visiting..:)

nice solution. keep it up.

ReplyDeletestring = raw_input()

ReplyDeleteS=[[0 for x in xrange(len(string))] for x in xrange(len(string))]

max_len=0

i=0

for x in string :

S[i][i]=int(x);

i=i+1;

for length in range(2,len(S)+1):

for i in range(0,len(S)-length+1):

j=i+length-1;

S[i][j]=S[i][(i+j)/2]+S[(i+j)/2+1][j]

if length%2==0 and S[i][(i+j)/2]==S[(i+j)/2+1][j]:

if length>max_len:

max_len=length

print max_len;

**python solution**

Please find the Python code. This code is more optimozed compared to above:

ReplyDeleteinp_str=raw_input()

temp=[int(x) for x in inp_str]

n=len(temp)

max_start=-1

max_end=-1

max_diff=0

for i in xrange(0,n-1):

start=i

for j in xrange(i+1,n,2):

end=j

diff=(end-start-1)/2

if sum(temp[start:start+diff+1])==sum(temp[start+diff+1:end+1]):

if (end-start>max_diff):

max_start=start

max_end=end

max_diff=end-start

print max_diff+1

This comment has been removed by the author.

ReplyDeletedef substr2N(str)

ReplyDeletea = Array.new

x= str.split("")

(0..((x.length)-1)).each {|i|

((i+1)..((x.length) - 1)).step(2) {|j|

a.push(x[i..j].join(""))

}

}

longest = 0

a.each {|i| x= i.split("")

if sum(x[0..((i.length)/2 -1)]) == sum(x[(i.length/2)..((i.length) -1)])

if i.length > longest

longest = i.length

end

end

}

longest

end

def sum(arr)

sum =0

arr.each{|i| sum += (i.to_i)}

sum

end

Please explain the algorithm... I didn't get it

ReplyDeleteThis comment has been removed by the author.

ReplyDeletedef getEqualSumSubstring(s):

ReplyDeletes2 = [int(x) for x in s]

n = len(s2)

if n%2 != 0: n = n - 1

while n != 0:

for i in range((len(s2) - n) + 1):

if sum(s2[i:n/2+i]) == sum(s2[n/2+i:n+i]):

return n

n = n - 2;

return n

Wow.. Such a great blog!! I am giving the reference of Amazon Store "Couponinformer" where you all get so much collection with superb prices. This website also giving wonderful offers. So that, Shop Online- Couponinformer is one of the shopping Store which provide best fashion accessories.Online Flipkart Shopping

ReplyDeleteHello, This is very help full post. Here is available https://www.couponhai.com/. Coupon Code, Discount code & Offer code. Thank You.

ReplyDelete