Test Case Failed Even Program Is Giving Correct Output

#1

#include
#include
using namespace std;
int max(int index1,int index2,int array[]){
int i=0,largest=INT_MIN;
for(i=index1;i<=index2;i++){
if(array[i]>largest){
largest=array[i];
}
}
return largest;
}
int index(int largest,int array[], int n){
int i,in;
for(i=0;i<n;i++){
if(largest==array[i]){
in=i;
}
}
return in;
}
int adj(int i,int array[],int n){
int j,start;
start=i;
for(j=i;j<n-1;j++){
if(array[j]<array[j+1]){
start=j+1;
}
else{
start=j;
break;
}
}
return start;
}
int rain_water(){
int n,i,k=0,space=0,start=0,water=0,j,largest=0,in=0,b=0;
cin>>n;
int tower[n];
for(i=0;i<n;i++){
cin>>tower[i];
}
for(i=0;i<n;i++){
if(tower[i]!=0 and k==0){
k=1;
start=i;
}
else if(k==1 and tower[i]==0 and i!=n-1){
space=1;
}
else if(space==1 and tower[i]!=0){
break;
}
}
if(i==n){
return 0;
}
else{
i=0,k=0;
for(i=start+1;i<n;i++){
if(tower[i]>=tower[start]){
k=1;
for(j=start+1;j<i;j++){
water=water+(tower[start]-tower[j]);
}
start=adj(i,tower,n);
b=1;
}
else if(i==n-1 and k==0){
while(start<n-1){
largest=max(start+1,n-1,tower);
in=index(largest,tower,n);
if(in==start+1){
start=start+1;
continue;
}
else{
break;
}
}
if(start<(n-1)){
for(j=start+1;j<in;j++){
water=water+(largest-tower[j]);
}
start=in;
b=1;
}

		}
		if(b==1 and i<n-1){
			k=0;
			b=0;
			i=start;
		}
	}
}
return water;

}
int main(){
int t,z;
cin>>t;
for(z=0;z<t;z++){
cout<<rain_water()<<endl;
}
return 0;
}

Please find the error in this program and why it failed test cases even though the program gives the correct output.

#2

hi @di5n7u_f87e18903cba617b,

EXPLANATION

An element of the array can store water if there are higher bars on left and right. We can find the amount of water to be stored in every element by finding the heights of bars on left and right sides. The idea is to compute the amount of water that can be stored in every element of array. For example, consider the array {3, 0, 0, 2, 0, 4}, we can store three units of water at indexes 1 and 2, and one unit of water at index 3, and three units of water at index 4.

A Simple Solution is to traverse every array element and find the highest bars on left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element. Time complexity of this solution is O(n2).

Naive Approach

int maxWater(int arr[], int n)
{

// To store the maximum water  
// that can be stored 
int res = 0; 

// For every element of the array 
for (int i = 1; i < n-1; i++) { 

    // Find the maximum element on its left 
    int left = arr[i]; 
    for (int j=0; j<i; j++) 
       left = max(left, arr[j]); 

    // Find the maximum element on its right    
    int right = arr[i]; 
    for (int j=i+1; j<n; j++) 
       right = max(right, arr[j]);  

   // Update the maximum water     
   res = res + (min(left, right) - arr[i]);    
} 

return res;

}

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.