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

Interviewstreet CouponDunia Palindrome Problem

Interviewstreet CouponDunia Palindrome Problem

Problem Statement

Given a string, determine whether it is palindrome or not. Output 1 for palindrome, and output 0 for not a palindrome.

A palindrome is a string that when reversed is equivalent to its original. Assume case is insensitive and then all non letters are ignored in calculating whether the string is palindrome.

Sample Input:
Dad
Sample Output:
1

Sample Input:
A man, a plan, a canal - Panama!
Sample Output:
1

Solution

#include<iostream>

#define MAX 1000
using namespace std;


int main()
{
 char s[MAX];
 cin>>s;
 int n=strlen(s);

 int i=0,j=n-1;
    while(i<j)
    {

              if(tolower(s[i])!=tolower(s[j]))
              break;
              i++;
              while(tolower(s[i])==s[i]&&(toupper(s[i])==s[i]))
              i++;
              j--;
              while((tolower(s[j])==s[j])&&(toupper(s[j])==s[j]))
              j--;

    }
    if(i>=j)
    cout<<1;
    else
    cout<<0;

}

Time Complexity: O(n)

InterviewStreet CouponDunia Count Pairs Problem: C++ code

CouponDunia Count Pairs Problem

Problem Statement

Given N numbers , [N<=10^5] we need to count the total pairs of numbers 

that have a difference of K. [K>0 and K<1e9]

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured 

to be distinct. 

Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:
3 

Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635
491595254 879792181 1069262793

Sample Output #01:
0 

Solution

#include<iostream>
#include<algorithm>

using namespace std;
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
int n,k;

cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];

qsort(a,n,sizeof(int),compare);

int seq=0;
for(int i=0;i<n;i++)
{
int key=a[i]+k;
if(((int*)bsearch(&key,a+i+1,n-i-1,sizeof(int),compare))!=NULL)
seq++;
} 

cout<<seq;

}

Time Complexity : O(nlogn)