The Interview Question Today#24(19-3-19)

Question:

Given the perimeter of a rectangle, the task is to find the maximum area of a rectangle which can be formed.

Example:

Input: perimeter = 15

Output: Maximum Area = 12

Solution:

Approach:

For the area to be maximum of any rectangle the difference of length and breadth must be minimal. So, in such case, the length must be ceil (perimeter / 4) and breadth will be floor(perimeter /4).

 Hence the maximum area of a rectangle with a given perimeter is equal to ceil(perimeter/4) * floor(perimeter/4).

C program:

#include<stdio.h>

// Function to find max area

float maxArea(float perimeter)

{

int length = (int)ceil(perimeter / 4);

int breadth = (int)floor(perimeter / 4);

// return area

printf("Length=%d \nBreath=%d\n",length,breadth);

return length * breadth;

}

int main()

{

float n;

printf("Enter the Perimeter\n");

scanf("%f",&n);

printf("Maximum Area = %f",maxArea(n));

return 0;

}

Output:

Enter the Perimeter

30

Length=8

Breath=7

Maximum Area = 56.000000

Read More

The Interview Question Today#23(18-3-19)

Question:
Given four integers a, b, c and d which signifies the number of four types of brackets.

A=> “((“
B=> “()”
C=> “)(“
D=> “))”

The task is to print any balanced bracket expression using all the given brackets. If we cannot form a balanced bracket expression then print -1. 

Examples:

Input: a = 3, b = 1, c = 4, d = 3

Output: (((((()()()()())))))()

Solution:
Approach: 
First check if the balanced bracket expression can be formed with the given number of brackets. We can form the expression if the number of A brackets is equal to the number of D brackets with any number of C brackets And B type brackets or if there are only type B brackets. Hence the combining condition will be:

(a == d && a) || (a == 0 && c == 0 && d == 0)

C program:

#include <stdio.h>

// Function to print balanced bracket expression if it is possible
int printBalancedExpression(int a, int b, int c, int d)
{
int i;
    if ((a == d && a) || (a == 0 && c == 0 && d == 0)) {

        for ( i = 1; i <= a; i++)
            printf("((");

        for ( i = 1; i <= b; i++)
            printf("()");
        for ( i = 1; i <= c; i++)
            printf(")(");

        for ( i = 1; i <= d; i++)
            printf("))");


    }

    else{
        printf(-1);
        return 0;}
        return 1;
}
int main()
{
    int a,b,c,d;
    printf("Enter Value of A:");
    scanf("%d",&a);
    printf("\nEnter Value of B:");
    scanf("%d",&b);
    printf("\nEnter Value of C:");
    scanf("%d",&c);
    printf("\nEnter Value of D:");
    scanf("%d",&d);
    printf("\n");
    if(printBalancedExpression(a, b, c, d)){
     printf("\tBalanced Brackets");
    }
    else{
     printf("\tUnBalanced Brackets");
    }
    return 0;
}

Output:
Enter Value of A:1

Enter Value of B:1

Enter Value of C:1

Enter Value of D:1

((())())        Balanced Brackets

Read More

The Interview Question Today#22(17-3-19)

Question:

C Program to print numbers from 1 to N without using the semicolon?

Solution:

#include<stdio.h>

#define N 10

int main(int num)

{

    if (num <= N && printf("%d ", num) && main(num + 1))

    {

    }

}

Read More

The Interview Question Today#20 (15-3-19)

Question:
A Program to check if strings are rotations of each other or not


Example:

INPUT
String1 = "ABCDE"
String2 = "DEABC"

OUTPUT
Strings are rotations of each other

Solution:

Approach:

1. Concatenate s1 with s1

2. Now, if s2 is a substring of above concatenation, then s1 and s2 are rotations of each other.


C program:


# include <stdio.h>
# include <string.h>
# include <stdlib.h>

/* Function checks if passed strings (str1 and str2) are rotations of each other */
int areRotations(char *str1, char *str2)
{
  int size1   = strlen(str1);
  int size2   = strlen(str2);
  char temp[200];
  void *ptr;

  if (size1 != size2)
     return 0;

  strcat(temp, str1);
  strcat(temp, str1);

  ptr = strstr(temp, str2);
  free(temp);
  if (ptr != NULL)
    return 1;
  else
    return 0;
}

int main()
{
    char str1[100];
    char str2[100];
    printf("Enter the First String: ");
    scanf("%s",str1);
    printf("Enter the Second String: ");
    scanf("%s",str2);


    if (areRotations(str1, str2))
       printf("Strings are rotations of each other");
    else
       printf("Strings are not rotations of each other");

    return 0;
}

Output:

Enter the First String: ABCD
Enter the Second String: CDAB
Strings are rotations of each other

Read More

The Interview Question Today#19(14-3-19)

Question:

Check if two given strings are isomorphic to each other

Example:

Input:  String1 = "aab"
           String2 = "xxy"
Output: Given String Are Ismorphic ('a' is mapped to 'x' and 'b' is mapped to 'y'.)

Solution:

Approach:

1) If lengths of str1 and str2 are not same, return false.
2) Do following for every character in str1 and str2
   a) If this character is seen first time in str1, 
      then current of str2 must have not appeared before.
      (i) If current character of str2 is seen, return false.
          Mark current character of str2 as visited.
      (ii) Store mapping of current characters.
   b) Else check if previous occurrence of str1[i] mapped

      to same character.

C program:

#include<stdio.h>
#define MAX_CHARS 256
#include<string.h>

// This function returns true if str1 and str2 are ismorphic
int areIsomorphic(char *str1,char *str2)
{
int i;
for(i=0;str1[i]!='\0';i++);
int m=i;

for(i=0;str2[i]!='\0';i++);
int n=i;

    if (m != n)
      return 0;

    // To mark visited characters in str2
    int marked[MAX_CHARS] = {0};

    int map[MAX_CHARS];
    memset(map, -1, sizeof(map));

    for ( i = 0; i < n; i++)
    {
        if (map[str1[i]] == -1)
        {
            if (marked[str2[i]] == 1)
                return 0;

               marked[str2[i]] = 1;

            map[str1[i]] = str2[i];
        }

        else if (map[str1[i]] != str2[i])
            return 0;
    }

    return 1;

}

int main()
{
    char str1[100];
    char str2[100];
    printf("Enter the First String: ");
    scanf("%s",str1);
    printf("Enter the Second String: ");
    scanf("%s",str2);

    if(areIsomorphic(str1,str2))
   printf("Given String Are Ismorphic\n");
   else{
    printf("Given String Are Not Ismorphic\n");
   }
   return 0;
}

Output:
Enter the First String: aaa
Enter the Second String: xxx
Given String Are Ismorphic

Read More

The Interview Question Today#17(12-3-19)

Question:

Write a Program to check whether two given strings are an anagram of each other or not. 

Example:

Input: String1: silent

           String2: listen

Output: The two strings are an anagram of each other


Solution:

Approach 1:

1) Create count arrays of size 256 for both strings. Initialize all values in count arrays as 0.
2) Iterate through every character of both strings and increment the count of character in the corresponding count arrays.

3) Compare count arrays. If both count arrays are the same, then return true.


Approach 2:

1)Compare the length of both strings if equal continue or else false and exit.
2) Sorting Both Strings.
3) Comparing them.
4) if equal then true or false.

C program://Approach 1

#include <stdio.h>
#define NO_OF_CHARS 256

/* function to check whether two strings are an anagram of each other */
int areAnagram(char* str1, char* str2)
{
    int count1[NO_OF_CHARS] = { 0 };
    int count2[NO_OF_CHARS] = { 0 };
    int i;

    for (i = 0; str1[i] && str2[i]; i++) {
        count1[str1[i]]++;
        count2[str2[i]]++;
    }
   if (str1[i] || str2[i])
        return 0;

    for (i = 0; i < NO_OF_CHARS; i++)
        if (count1[i] != count2[i])
            return 0;

    return 1;
}
int main()
{
    char str1[100];
    char str2[100];
    printf("Enter the First String: ");
    scanf("%s",str1);
    printf("Enter the Second String: ");
    scanf("%s",str2);

    if (areAnagram(str1, str2))
        printf("The two strings are an anagram of each other");
    else
        printf("The two strings are not an anagram of each other");

    return 0;

}

Output:

Enter the First String: amit
Enter the Second String: tima

The two strings are an anagram of each other

C program: //Appoarch 2.

#include <stdio.h>
#include<stdlib.h>
#include<string.h>

void main()
{
    printf("Enter 2 strings ");
    char s1[30],s2[30];
    scanf("%s",s1);
    scanf("%s",s2);
    int m=strlen(s1);
    int n=strlen(s2);
    if(m!=n){// Comparing the Length.
        printf("Strings are not anagram case 1\n");
        exit(0);
    }
//Sorting Both Array using Bubble Sort.
    int i,j,flag=0;
   char temp;
   for(i=0;i<m-1;i++)
  {
      for(j=0;j<n-i-1;j++)
        if(s1[j]>s1[j+1])
        {   temp=s1[j];
            s1[j]=s1[j+1];
            s1[j+1]=temp;
        }
  }

    for(i=0;i<m-1;i++)
     {

        for(j=0;j<n-i-1;j++)
            if(s2[j]>s2[j+1])
            {   //printf("Hello");
                temp=s2[j];
                s2[j]=s2[j+1];
                s2[j+1]=temp;
        }
    }



//Comparing Both The Array.
    for(i=0;i<n;i++){
        if(s1[i]!=s2[i])
            flag=2;
    }
    if(flag==2)
        printf("Strings are not anagram\n");
    else
        printf("Strings are anagram\n");


}

Java: Approach 2
import java.util.Arrays;
import java.util.Scanner;

/*
 * A way to check if two Strings are anagram or not in Java
 * return true, if both Strings are anagram. 
 * else false, 
 * And it is case Sensitive 
 @JavaAbhigyan
 */

public class anagram {
private static Scanner s;
private static String str1,str2;
private static boolean ans;
public static boolean iAnagram(String word, String anagram)
{
char[] charFromWord = word.toCharArray();
char[] charFromAnagram = anagram.toCharArray();
Arrays.sort(charFromWord); Arrays.sort(charFromAnagram);

return Arrays.equals(charFromWord, charFromAnagram); 
}
public static void main(String[] args) {
s = new Scanner(System.in);
System.out.println("Enter the Main String\n");
str1 = s.nextLine();
System.out.println("Enter the test String\n");
    str2=s.nextLine();
ans = iAnagram(str1, str2);
System.out.println("Enter String:"+str1+" And String:"+str2+" are Anagram:"+ans);
}

}

Read More

The Interview Question Today#16(11-3-19)

Question:

Given an array arr[] of integers, find out the maximum difference between any two elements such that larger element appears after the smaller number.

Example:

Input : arr = {2, 3, 10, 6, 4, 8, 1}

Output : 8 (The maximum difference is between 10 and 2).

Solution:

Approach:

minElementTillNow will be initialise to arr[0].
Iterate over  arr[]
If current element is greater than minElementTillNow
calculate the difference.
If the difference is greater than maxDifference then update the maxDifference.
If current element is lesser than minElementTillNow
update minElementTillNow with current element.
We will get maxDifference in the end.

C program:

#include<stdio.h>

    // Create a diff array of size n-1. The array will hold

    //  the difference of adjacent elements

int maxDiff(int arr[], int n)

{

    int diff[n-1],i;

    for (i=0; i < n-1; i++)

        diff[i] = arr[i+1] - arr[i];

    int max_diff = diff[0];

    for (i=1; i<n-1; i++)

    {

        if (diff[i-1] > 0)

            diff[i] += diff[i-1];

        if (max_diff < diff[i])

            max_diff = diff[i];

    }

    return max_diff;

}

int main()

{

    int arr[100],i,n;

    printf("Enter The Number of Elements U Want to Insert ");

    scanf("%d",&n);

    printf("\nEnter the Elements\n");

    for(i=0;i<n;i++){

        scanf("%d",&arr[i]);

    }

    printf("Maximum difference is %d",  maxDiff(arr,n));

    return 0;

}

Output:

Enter The Number of Elements U Want to Insert 5

Enter the Elements

2

5

6

60

20

Maximum difference is 58

Read More

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

Question:
Given an array a, we have to find maximum product possible with the subset of elements present in the array.

Examples:

Input : a[] = { -1, -1, -2, 4, 3 }
Output : 24( Maximum product will be ( -2 * -1 * 4 * 3 ) = 24)

Approach:

1. If there are even number of negative numbers and no zeros, the result is simply a product of all
2. If there are an odd number of negative numbers and no zeros, the result is the product of all except the largest valued negative number.
3. If there are zeros, the result is the product of all except these zeros with one exceptional case. The exceptional case is when there is one negative number and all other elements are 0. In this case, the result is 0.

C program 

#include <stdio.h>

int maxProductSubset(int a[], int n)

{

    if (n == 1)

        return a[0];

    // Find count of negative numbers, count of zeros, maximum valued negative number

    // and product of non-zero numbers

    int max_neg =-999;

    int count_neg = 0, count_zero = 0;

    int prod = 1,i;

    for ( i = 0; i < n; i++) {

        // If number is 0, we don't multiply it with product.

        if (a[i] == 0) {

            count_zero++;

            continue;

        }

        // Count negatives and keep track of maximum valued negative.

        if (a[i] < 0) {

            count_neg++;

            max_neg = max(max_neg, a[i]);

        }

        prod = prod * a[i];

    }

    if (count_zero == n)

        return 0;

    if (count_neg & 1) {

        // Exceptional case: There is only negative and all other are zeros

        if (count_neg == 1 &&

            count_zero > 0 &&

            count_zero + count_neg == n)

            return 0;

        // Otherwise result is product of all non-zeros divided by maximum valued negative.

        prod = prod / max_neg;

    }

    return prod;

}

int max(int a,int b){

if(a>b)

{

    return a;

}

return b;

}

int main()

{

    int arr[100];

    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("Maximum Product= %d",maxProductSubset(arr, n));

    return 0;

}

Output:

Enter the Number of Elements present: 5

Enter the values of Elements

Elements 1:1

Elements 2:2

Elements 3:0

Elements 4:-1

Elements 5:-2

Maximum Product= 4

Read More

The Interview Question Today#14(9-3-19)

Question
Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[].

Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.

Solution

Approach:

ALGORITHM MinDistance(A[0..n - 1])

//Input: Array A[0..n - 1] of numbers

//Output: Minimum distance between two of its elements

dmin ← ∞

for i ← 0 to n - 1 do

forj ← 0 to n - 1 do

ifi = j and |A[i] - A[j]| < dmin

dmin← |A[i] - A[j]|

return dmin

C program:

// C program to Find the minimum// distance between two numbers

#include <stdio.h>

#include <stdlib.h> // for abs() Which calculate the difference between the //location in array 

int minDist(int arr[], int n, int x, int y)

{

   int i, j;

   int min_dist =30000;

   for (i = 0; i < n; i++)

   {

     for (j = i+1; j < n; j++)

     {

         if( (x == arr[i] && y == arr[j] ||

              y == arr[i] && x == arr[j]) && min_dist > abs(i-j))

         {

              min_dist = abs(i-j);

         }

     }

   }

   return min_dist;

}

int main()

{

    int arr[100];

    int n,i;

    int x;

    int y;

printf("Enter the no elements required in array\n ");

scanf("%d",&n);

printf("Enter the elements\n");

for(i=0;i<n;i++)

{

    scanf("%d",&arr[i]);

 }

printf("Enter the elements whose distance u want\n");

scanf("%d %d",&x,&y);

printf("Minimum distance between %d and %d is %d\n",x, y,minDist(arr, n, x, y));

    return 0;

} 

Output:

Enter the no elements required in array

 5

Enter the elements

1

2

3

4

5

Enter the elements whose distance u want

2

5

Minimum distance between 2 and 5 is 3

Read More

The Interview Question Today#13(8-3-19)

Question:
Find longest bitonic subarray in an array

Example:

Input: A[] = {12, 4, 78, 90, 45, 23}

Output: the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.



Approach:

Let us consider the array {12, 4, 78, 90, 45, 23} to understand the solution.
1) Construct an auxiliary array inc[] from left to right such that inc[i] contains the length of the nondecreasing subarray ending at arr[i].
For for A[] = {12, 4, 78, 90, 45, 23}, inc[] is {1, 1, 2, 3, 1, 1}

2) Construct another array dec[] from right to left such that dec[i] contains the length of nonincreasing subarray starting at arr[i].
For A[] = {12, 4, 78, 90, 45, 23}, dec[] is {2, 1, 1, 3, 2, 1}.

3) Once we have the inc[] and dec[] arrays, all we need to do is find the maximum value of (inc[i] + dec[i] – 1).
For {12, 4, 78, 90, 45, 23}, the max value of (inc[i] + dec[i] – 1) is 5 for i = 3.


C program:
#include <stdio.h>

// Function to find length of Longest Bitonic Subarray in an array
int findBitonicSubarray(int A[], int n)
{
// I[i] stores the length of the longest increasing sub-array ending at A[i]
int I[n + 1],i;
I[0] = 1;
for ( i = 1; i <= n; i++) {
I[i] = 1;
if (A[i-1] < A[i])
I[i] = I[i-1] + 1;
}

// D[i] stores the length of the longest decreasing sub-array starting with A[i]
int D[n + 1];
D[n] = 1;
for ( i = n - 1; i >= 0; i--) {
D[i] = 1;
if (A[i] > A[i+1])
D[i] = D[i+1] + 1;
}

int lbs_len = 1;
int beg = 0, end = 0;

for ( i = 0; i <= n; i++)
{
if (lbs_len < I[i] + D[i] - 1)
{
lbs_len = I[i] + D[i] - 1;
beg = i - I[i] + 1;
end = i + D[i] - 1;
}
}

printf("The length of longest bitonic sub-array is %d\n", lbs_len);
printf("The longest bitonic sub-array is [%d...... %d]", beg, end);

return lbs_len;
}

// main function
int main(void)
{
int arr[100] ;
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]);
    }

findBitonicSubarray(arr,n - 1);

return 0;
}

Output:
Enter the Number of Elements present: 5

Enter the values of Elements
Elements 1:2

Elements 2:3

Elements 3:4

Elements 4:2

Elements 5:1
The length of longest bitonic sub-array is 5
The longest bitonic sub-array is [0...... 4]

Read More

The Interview Question Today#12(7-3-19)

Question:
Given an array of n integers arr[], construct a Product Array such that Product array prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator

Example :

Input:    arr[] = {10, 3, 5, 6, 2}
Output: prod[] = {180, 600, 360, 300, 900}

Approach:
1) Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].
2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].
3) To get prod[], multiply left[] and right[].

C program:

#include <stdio.h>

// Function to replace each element of the array with the product  of every other element without //using the division operator
void findProduct(int arr[], int n)
{
int left[n], right[n];
int i,j;

// left[i] stores the product of all elements in the sub-array[0..i-1]
left[0] = 1;
for ( i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];

// right[i] stores the product of all elements in sub-array[i+1..n-1]
right[n - 1] = 1;
for ( j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];

// replace each element with product of its left and right sub-array
for ( i = 0; i < n; i++)
arr[i] = left[i] * right[i];
}

int main(void)
{
int arr[100];
        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]);
    }


findProduct(arr, n);
for ( i = 0; i < n; i++)
printf("%d ", arr[i]);

return 0;
}

Output:

Enter the Number of Elements present: 5

Enter the values of Elements

Elements 1:1

Elements 2:2

Elements 3:3

Elements 4:4

Elements 5:5

120 60 40 30 24

Read More

The Interview Question Today#11(6-3-19)

Question:
Find a majority element in an array of size n

Examples :

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output: 4

Approach:
int majorityElementNaive(int A[], int n)
{
// check if A[i] is majority element or not
for (int i = 0; i <= n/2; i++)
{
int count = 1;
for (int j = i + 1; j < n; j++) {
if (A[j] == A[i]) {
count++;
}
}

if (count > n/2) {
return A[i];
}
}

return -1;

}

C program: 
#include<stdio.h>
// Function to find Majority element in an array
void findMajority(int arr[], int n)
{
    int i,j;
    int maxCount = 0;
    int index = -1; // sentinels
    for( i = 0; i < n; i++)
    {
        int count = 0;
        for( j = 0; j < n; j++)
        {
            if(arr[i] == arr[j])
            count++;
        }

        // update maxCount if count of current element is greater
        if(count > maxCount)
        {
            maxCount = count;
            index = i;
        }
    }

    // if maxCount is greater than n/2 return the corresponding element
    if (maxCount > n/2)
       printf("Majority Element=%d\n",arr[index]);

    else
        printf("No Majority Element");
}

int main()
{
    int arr[100];
    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]);
    }

    findMajority(arr, n);

    return 0;
}
Output:
Enter the Number of Elements present: 5

Enter the values of Elements
Elements 1:1

Elements 2:2

Elements 3:1

Elements 4:2

Elements 5:1
Majority Element=1

Read More

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 }

Read More

The Interview Question Today#9(4-3-19)

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

Read More