The Interview Question Today#10(5-3-19)

Question:  

 Given an unsorted array of integers, find a continuous subarray which adds to a given number.

Example:

Input:

A[]={3,4,-7,1,3}
Sum=4
Output:
Subarrays with given sum are   {4}   {1,3}

Approach:

1. The idea is to keep adding all the elements to the currSum.
2. Keep checking if the currSum<Sum
3. If currSum gets greater than the Sum then start reducing the currSum.
4. from the beginning of the array using “start” if any time currSum=Sum, Stop and return
 

C program:
#include <stdio.h>

void print(int arr[], int i, int j)
{
    int k;
printf("[%d..%d] -- { ", i, j);
for ( 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)
{
    int i,j;
for ( i = 0; i < n; i++)
{
int sum_so_far = 0;

// consider all sub-arrays starting from i and ending at j
for ( j = i; j < n; j++)
{
sum_so_far += arr[j];


if (sum_so_far == sum) {
print(arr, i, j);
}
}
}
}

int main()
{
int arr[100];
int sum;

int n,i;
printf("Enter the Number of Elements present: ");
    scanf("%d",&n);
    printf("\nEnter the values of Elements");
    for(i=0;i<n;i++)
    {
        printf("\nElements %d:",i+1);
        scanf("%d",&arr[i]);
    }
    printf("Enter the Sum U What To find\n");
    scanf("%d",&sum);
findSubarrays(arr, n, sum);

return 0;
}

Output:
Enter the Number of Elements present: 10

Enter the values of Elements
Elements 1:1

Elements 2:2

Elements 3:3

Elements 4:4

Elements 5:-2

Elements 6:-1

Elements 7:-3

Elements 8:-5

Elements 9:5

Elements 10:-4
Enter the Sum U What To find
0
[0..9] -- { 1 2 3 4 -2 -1 -3 -5 5 -4 }
[7..8] -- { -5 5 }