see attached file
On Sun, Oct 31, 2010 at 4:27 PM, snehal jain <[email protected]> wrote:
> Find longest interval:-
> We are given with two arrays A and B..each of size
> N...elements of array contains either 1 or 0...
> we have to find such an interval (p,q)(inclusive) such that the sum of
> all
> the elements of A (between this interval) and sum of all elements of
> B
> (between this interval ) is equal...
> i.e.
> a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include<stdio.h>
#define S 14
#define Z -99
int main(){
int a[S] = {0,0,0,1,0,1,0,0,1,1,1,1,0,1};
// int b[S] = {1,0,0,0,1,1,1,1,0,1,1,1,0,0};
// int b[S] = {1,0,1,0,1,1,1,1,0,1,1,1,0,0};
int b[S] = {0,0,0,0,1,0,0,1,0,1,1,0,0,0};
int suma[S],sumb[S],diff[S];
int diffL[S]={-1,Z,Z,Z,Z,Z,Z,Z,Z,Z,Z,Z,Z,Z};
int diffLR[S]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int i;
for(i=0;i<S;i++){
if(i==0){
suma[0]=a[0];
sumb[0]=b[0];
}
else{
suma[i]=suma[i-1]+a[i];
sumb[i]=sumb[i-1]+b[i];
}
diff[i]=sumb[i]-suma[i];
if(diffL[diff[i]]== Z ){
diffL[diff[i]]=i;
diffLR[diff[i]]=0;
}else{
diffLR[diff[i]] = (i-diffL[diff[i]]);
}
}
/********** Print summary of what's been done ***************/
printf("\nIndex (i): \n");
for(i=0;i<S;i++){
printf("[%d]\t",i);
}
printf("\nA: \n");
for(i=0;i<S;i++){
printf("%d\t",a[i]);
}
printf("\nB: \n");
for(i=0;i<S;i++){
printf("%d\t",b[i]);
}
printf("\n\nsum_A: sum_A[i]=A[0]+A[1]+..+A[i] \n");
for(i=0;i<S;i++){
printf("%d\t",suma[i]);
}
printf("\n\nsum_B: sum_B[i]=B[0]+B[1]+..+B[i] \n");
for(i=0;i<S;i++){
printf("%d\t",sumb[i]);
}
printf("\n\ndiff : diff[i]=sum_B[i]-sum_A[i] \n");
for(i=0;i<S;i++){
printf("%d\t",diff[i]);
}
printf("\n\ndiffL: diffL[i]= Position of first occurrence of i in diff; %d if never occurred \n",Z);
for(i=0;i<S;i++){
printf("%d\t",diffL[i]);
}
printf("\n\ndiffLR: diffLR[i] = Length of interval formed by first & latest(rightmost) occurrence positions of i in diff\n");
for(i=0;i<S;i++){
printf("%d\t",diffLR[i]);
}
/******************************************************************/
{
printf("\nFinding longest interval (largest of diffLR)..\n");
int max = -1;
int maxpos = -1;
for(i=0;i<S;i++){
if(diffLR[i]>max){
max=diffLR[i],maxpos=i;
}
}
if(maxpos>-1){
int p = diffL[maxpos] + 1;
int q = diffL[maxpos] + diffLR[maxpos];
printf("Max interval length = %d \n",max);
printf("a[%d]+...+a[%d] = b[%d]+...+b[%d] = %d \n",p,q,p,q,suma[q]-suma[p]+a[p]);
}
else{
printf("No interval possible\n");
}
}
return 0;
}
