Check if two strings are anagrams
July 3, 2012
One Definition Rule (ODR) in C++
July 4, 2012

Continuous sub-array with given sum

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

Your email address will not be published. Required fields are marked *