Jul 042012
 

Given an array of positive integers and a number ‘k’. Find continuous subarray whith sum of all the elements = k. For example..

Array                   k            Output
---------------------  ------      --------------
{2, 4, 17, 9, 6, 3}    18          FOUND. arr[3] thru arr[5] 
{1, 0, 4, 0, 2}        7           FOUND. arr[0] thru arr[4]
{1, 0, 4, 0, 2}        3           NOT FOUND.

Solution:

Method-1: Bruite-Force (Consider all sub arrays)

Algorithm:

Consider all subarrays one by one. 
If the sum = k 
    print the indexes and return TRUE
else
    return FALSE

Code:

    /* Print the Indexes of the sub array and return true if founds 
     * a continuous sub-array with sum = k
     * else  returns false. 
     * Parameters: arr, n - Array and size of array. 
     */
    int findSubArray(int *arr, int n, int k)
    {
        // Loop will check for sub-array starting at i.
        for (int i = 0; i<n; i++)
        {
            int sum = 0;

            for (int j = i; j < n; j++)
            {
                sum = sum + arr[j];

                if (sum == k){
                    printf ("FOUND: %d - %d", i, j);
                    return true;
                }

                // Don't need to check further if sum > k.. 
                // because array does not have -ve integers  
                if (sum > k)
                    break;
            }
        }

        printf("NOT FOUND");
        return false;
    }

Time complexity: O(n2)
(There are n sub-arrays with 1, 2, 3, … n. elements and we are considering all of them)

Method-2: Using Single Iteration

Algorithm:

Let 'sum' Indicate the sum of sub-array under consideration.

sum = arr[0] 
FOR i= 1 TO n-1
    IF sum IS EQUAL TO k
          FOUND the sub array, print the indexes and return.
    IF sum IS GREATER THAN k
          remove the initial elements from SUM until it becomes < k

Print NOT FOUND

Code:

    /* Print the Indexes of the sub array and return true if founds 
     * a continuous sub-array with sum = k
     * else  returns false. 
     * Parameters: arr, n - Array and size of array. 
     */
    int findSubArray(int *arr, int n, int k)
    {
        int sum = 0;

        int startIdx = 0; // Represent the Start Index of sub-array

        for (int i = 0; i <= n; i++)
        {
            sum = sum + arr[i];

            // If curr_sum becomes equal to sum, then return true
            if (sum == k)
            {
                 printf ("FOUND: %d - %d", startIdx, i-1); 
                 return true;
            }

            while (sum > k && startIdx < i)
            {
                sum = sum - arr[startIdx];
                startIdx++;
            }
        }

        printf("NOT FOUND");
        return false;
    }

Time complexity: O(n)

Please let me know your comments / feedback / suggestions.

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)