/* An efficient program to print subarray with sum as given sum */
#include<stdio.h>
 
/* Returns true if the there is a subarray of arr[] with sum equal to 'sum'
   otherwise returns false.  Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;
 
    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }
 
        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }
 
        // Add this element to curr_sum
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
 
    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}
 
// Driver program to test above function
int main()
{
    int arr[] =  {3, 34, 4, 12, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 9;
    subArraySum(arr, n, sum);
    return 0;
}
 

LyogQW4gZWZmaWNpZW50IHByb2dyYW0gdG8gcHJpbnQgc3ViYXJyYXkgd2l0aCBzdW0gYXMgZ2l2ZW4gc3VtICovCiNpbmNsdWRlPHN0ZGlvLmg+CgovKiBSZXR1cm5zIHRydWUgaWYgdGhlIHRoZXJlIGlzIGEgc3ViYXJyYXkgb2YgYXJyW10gd2l0aCBzdW0gZXF1YWwgdG8gJ3N1bScKICAgb3RoZXJ3aXNlIHJldHVybnMgZmFsc2UuICBBbHNvLCBwcmludHMgdGhlIHJlc3VsdCAqLwppbnQgc3ViQXJyYXlTdW0oaW50IGFycltdLCBpbnQgbiwgaW50IHN1bSkKewogICAgLyogSW5pdGlhbGl6ZSBjdXJyX3N1bSBhcyB2YWx1ZSBvZiBmaXJzdCBlbGVtZW50CiAgICAgICBhbmQgc3RhcnRpbmcgcG9pbnQgYXMgMCAqLwogICAgaW50IGN1cnJfc3VtID0gYXJyWzBdLCBzdGFydCA9IDAsIGk7CgogICAgLyogQWRkIGVsZW1lbnRzIG9uZSBieSBvbmUgdG8gY3Vycl9zdW0gYW5kIGlmIHRoZSBjdXJyX3N1bSBleGNlZWRzIHRoZQogICAgICAgc3VtLCB0aGVuIHJlbW92ZSBzdGFydGluZyBlbGVtZW50ICovCiAgICBmb3IgKGkgPSAxOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICAvLyBJZiBjdXJyX3N1bSBleGNlZWRzIHRoZSBzdW0sIHRoZW4gcmVtb3ZlIHRoZSBzdGFydGluZyBlbGVtZW50cwogICAgICAgIHdoaWxlIChjdXJyX3N1bSA+IHN1bSAmJiBzdGFydCA8IGktMSkKICAgICAgICB7CiAgICAgICAgICAgIGN1cnJfc3VtID0gY3Vycl9zdW0gLSBhcnJbc3RhcnRdOwogICAgICAgICAgICBzdGFydCsrOwogICAgICAgIH0KCiAgICAgICAgLy8gSWYgY3Vycl9zdW0gYmVjb21lcyBlcXVhbCB0byBzdW0sIHRoZW4gcmV0dXJuIHRydWUKICAgICAgICBpZiAoY3Vycl9zdW0gPT0gc3VtKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmICgiU3VtIGZvdW5kIGJldHdlZW4gaW5kZXhlcyAlZCBhbmQgJWQiLCBzdGFydCwgaS0xKTsKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgfQoKICAgICAgICAvLyBBZGQgdGhpcyBlbGVtZW50IHRvIGN1cnJfc3VtCiAgICAgICAgaWYgKGkgPCBuKQogICAgICAgICAgY3Vycl9zdW0gPSBjdXJyX3N1bSArIGFycltpXTsKICAgIH0KCiAgICAvLyBJZiB3ZSByZWFjaCBoZXJlLCB0aGVuIG5vIHN1YmFycmF5CiAgICBwcmludGYoIk5vIHN1YmFycmF5IGZvdW5kIik7CiAgICByZXR1cm4gMDsKfQoKLy8gRHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbgppbnQgbWFpbigpCnsKICAgIGludCBhcnJbXSA9ICB7MywgMzQsIDQsIDEyLCA1LCAyfTsKICAgIGludCBuID0gc2l6ZW9mKGFycikvc2l6ZW9mKGFyclswXSk7CiAgICBpbnQgc3VtID0gOTsKICAgIHN1YkFycmF5U3VtKGFyciwgbiwgc3VtKTsKICAgIHJldHVybiAwOwp9Cg==