Sunday, 27 May 2012

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..:)

10 comments:

  1. nice solution. keep it up.

    ReplyDelete
  2. string = raw_input()
    S=[[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**

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

    inp_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

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. def substr2N(str)
    a = 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

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

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. def getEqualSumSubstring(s):
    s2 = [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

    ReplyDelete
  9. 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

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

    ReplyDelete