Problem: Given an unsorted array of integers, find a subarray which adds to a given number. If there are more than one subarrays with the sum as the given number, print any of them.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <stdio.h> // Utility function to print the sub-array arr[i,j] void print(int arr[], int i, int j) { printf("[%d..%d] -- { ", i, j); for (int k = i; k <= j; k++) { printf("%d ", arr[k]); } printf("}\n"); } // Function to find sub-arrays with given sum in an array void findSubarrays(int arr[], int n, int sum) { for (int i = 0; i < n; i++) { int sum_so_far = 0; // consider all sub-arrays starting from i and ending at j for (int j = i; j < n; j++) { // sum of elements so far sum_so_far += arr[j]; // if sum so far is equal to the given sum if (sum_so_far == sum) { print(arr, i, j); } } } } // main function int main() { int arr[] = { 3, 4, -7, 1, 3, 3, 1, -4 }; int sum = 7; int n = sizeof(arr)/sizeof(arr[0]); findSubarrays(arr, n, sum); return 0; } |
Program Output
1 2 3 4 | [0..1] -- { 3 4 } [0..5] -- { 3 4 -7 1 3 3 } [3..5] -- { 1 3 3 } [4..6] -- { 3 3 1 } |
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
