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.