#include<stdio.h>
int subArraySum(int a[], int n, int sum)
{
int i, s_index=0, curr_sum=a[0];
for(i=1; i<n; i++)
{
if(curr_sum==sum)
{
printf("starting and ending index are: %d %d", s_index
, i
-1); return 1;
}
else if(curr_sum<sum)
curr_sum=curr_sum+a[i];
else
{
if(a[i]<0)
{
curr_sum=curr_sum+a[i];
if(curr_sum==sum) //tricky step -> after subtracting check if this new curr_sum==sum or not
{
printf("starting and ending index are: %d %d", s_index
, i
); return 1;
}
}
else
{
curr_sum=curr_sum-a[s_index];
s_index=s_index+1;
if(curr_sum==sum) //tricky step -> after subtracting check if this new curr_sum==sum or not
{
printf("starting and ending index are: %d %d", s_index
, i
-1); return 1;
}
curr_sum=curr_sum+a[i];
}
}
}
}
int main()
{
int arr[]={2, 8, 5, -7};
int n = sizeof(arr)/sizeof(arr[0]);
int sum = 6;
subArraySum(arr, n, sum);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KCmludCBzdWJBcnJheVN1bShpbnQgYVtdLCBpbnQgbiwgaW50IHN1bSkKewogICAgIGludCBpLCBzX2luZGV4PTAsIGN1cnJfc3VtPWFbMF07CiAgICAgZm9yKGk9MTsgaTxuOyBpKyspCiAgICAgewogICAgICAgICAgICAgIGlmKGN1cnJfc3VtPT1zdW0pCiAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpbnRmKCJzdGFydGluZyBhbmQgZW5kaW5nIGluZGV4IGFyZTogJWQgJWQiLCBzX2luZGV4LCBpLTEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIGVsc2UgaWYoY3Vycl9zdW08c3VtKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjdXJyX3N1bT1jdXJyX3N1bSthW2ldOwogICAgICAgICAgICAgIGVsc2UgCiAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICBpZihhW2ldPDApCiAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGN1cnJfc3VtPWN1cnJfc3VtK2FbaV07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZihjdXJyX3N1bT09c3VtKSAgICAgICAgICAgICAvL3RyaWNreSBzdGVwICAtPiBhZnRlciBzdWJ0cmFjdGluZyBjaGVjayBpZiB0aGlzIG5ldyBjdXJyX3N1bT09c3VtIG9yIG5vdAogICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW50Zigic3RhcnRpbmcgYW5kIGVuZGluZyBpbmRleCBhcmU6ICVkICVkIiwgc19pbmRleCwgaSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICBjdXJyX3N1bT1jdXJyX3N1bS1hW3NfaW5kZXhdOwogICAgICAgICAgICAgICAgICAgICAgc19pbmRleD1zX2luZGV4KzE7CiAgICAgICAgICAgICAgICAgICAgICBpZihjdXJyX3N1bT09c3VtKSAgICAgICAgICAgICAvL3RyaWNreSBzdGVwICAtPiBhZnRlciBzdWJ0cmFjdGluZyBjaGVjayBpZiB0aGlzIG5ldyBjdXJyX3N1bT09c3VtIG9yIG5vdAogICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByaW50Zigic3RhcnRpbmcgYW5kIGVuZGluZyBpbmRleCBhcmU6ICVkICVkIiwgc19pbmRleCwgaS0xKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gMTsKICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgIGN1cnJfc3VtPWN1cnJfc3VtK2FbaV07CiAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICB9ICAgICAgICAgICAgICAKICAgICB9CiAgICAgcHJpbnRmKCJObyBzdWItYXJyYXkgZm91bmQiKTsgICAgIAp9CgppbnQgbWFpbigpCnsKICAgIGludCBhcnJbXT17MiwgOCwgNSwgLTd9OwogICAgaW50IG4gPSBzaXplb2YoYXJyKS9zaXplb2YoYXJyWzBdKTsKICAgIGludCBzdW0gPSA2OwogICAgc3ViQXJyYXlTdW0oYXJyLCBuLCBzdW0pOwogICAgZ2V0Y2hhcigpOwogICAgcmV0dXJuIDA7Cn0K