Interviewstreet CouponDunia GetEqualSumSubString Problem

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;
}

Time Complexity: O(n2)



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