QUESTION:
Program to find the maximum amount of water that can be trapped within a given set of bars. (Trapping rainwater problem)
Examples:
Input: arr[] = {2, 0, 0,2}
Output: 4
The structure is like below
0
|
1
|
2
|
0
|
0
|
4
|
3
|
0
|
We can trap 4 units of water in the middle gap.
SOLUTION:
Approach:
1: With given towerHeight array, create 2 arrays, maxSeenRight and maxSeenLeft.
maxLeft[i] – max height on left side of Tower[i].
maxRight[i] – max height on right side of Tower[i].
2: Calculate for each tower:
rainwater = rainwater + Max(Min(maxLeft[i], maxRight[i]) – towerHeight[i], 0);
C program:
#include<stdio.h>
int findWater(int arr[], int n)
{
int left[n];
int right[n];
int water = 0,i;
left[0] = arr[0];
for ( i = 1; i < n; i++)
left[i] = max(left[i-1], arr[i]);
right[n-1] = arr[n-1];
for ( i = n-2; i >= 0; i--)
right[i] = max(right[i+1], arr[i]);
// Calculate the accumulated water element by element
// consider the amount of water on i'th bar, the
// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i] .
for ( i = 0; i < n; i++)
water += min(left[i],right[i]) - arr[i];
return water;
}
int max(int a,int b){
if(a>b)
{
return a;
}
return b;
}
int min(int a,int b){
if(a<b)
{
return a;
}
return b;
}
int main()
{
int arr[100];
int n,i;
printf("Enter the Number of Bars present: ");
scanf("%d",&n);
printf("\nEnter the Height of Bars");
for(i=0;i<n;i++)
{
printf("\nBar %d:",i+1);
scanf("%d",&arr[i]);
}
printf("Maximum water that can be accumulated is= %d ",findWater(arr, n));
return 0;
}
OUTPUT:
Enter the Number of Bars present: 4
Enter the Height of Bars
Bar 1:2
Bar 2:0
Bar 3:0
Bar 4:2
Maximum water that can be accumulated is= 4
0 comments:
Post a Comment