CONCEPTS USED:

Searching

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT(SIMPLIFIED):

Given an array A of unique heights of buildings. The sun is facing buildings from left to right, print the number of buildings facing the sun directly.

See original problem statement here

For Example :

Input : arr[] = [7, 4, 8, 2, 9]

Output : 3 

Explanation : (7, 8 and 9) are facing sun directly while (4 and 2) are hidden after 7 and 8

SOLVING APPROACH:

  1. The idea is to learn react online to traverse the array from left to right and keep incrementing the count whenever we find the tallest building of the array up till now.

  2. Initialise tallest as -1 and count as 0.

  3. Traverse the array and if an element is greater than tallest then update it as tallest and increment count by 1.

  4. Finally, print the value of count.

ILLUSTRATION:

A[] = [7, 4, 8, 2, 9]
count = 0
tallest = -1

i = 0
Since A[0] > tallest
tallest = A[0] = 7
count++ => count = 1
i++ 

i = 1
Since A[1] <= tallest
i++

i = 2
Since A[2] > tallest
tallest = A[2] = 8
count++ => count = 2
i++

i = 3
Since A[3] <= tallest
i++

i = 4
Since A[4] > tallest 
tallest = A[4] = 9
count++ => count = 3
i++

Since i = 5
stop

So total 3 buildings are facing the sun directly.

SOLUTIONS:


#include <stdio.h>

int main()
{
  int t; scanf("%d", &t);
  while(t--){
    int n; scanf("%d", &n);
    int arr[n];

    //mark tallest building as -1 
    int max_ele = -1, count = 0;
    for(int i=0; i<n; i++){
      scanf("%d", &arr[i]);

    /* check if current building is taller than the tallest building
    if Yes increment count and mark it as tallest building else skip */
      if(arr[i] > max_ele){
        max_ele = arr[i];
        count++;
      }
    }
    printf("%d\n",count);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    int arr[n];

    //mark tallest building as -1 
    int max_ele = -1, count = 0;
    for(int i=0; i<n; i++){
      cin>>arr[i];

    /* check if current building is taller than the tallest building
    if Yes increment count and mark it as tallest building else skip */
      if(arr[i] > max_ele){
        max_ele = arr[i];
        count++;
      }
    }
    cout<<count<<"\n";
  }
  return 0;
}

import java.util.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t != 0){
      int n = sc.nextInt();
      int arr[] = new int[n];

      //mark tallest building as -1 
      int max_ele = -1, count = 0;
      for(int i=0; i<n; i++){
        arr[i] = sc.nextInt();

      /* check if current building is taller than the tallest building
      if Yes increment count and mark it as tallest building else skip */
        if(arr[i] > max_ele){
          max_ele = arr[i];
          count++;
        }
      }
      System.out.println(count);
      t--;
    }
  }
}

Space Complexity: O(1)

Previous post Anagram or Not (IMAGE NOT ADDED)
Next post Factorial Zeros

Leave a Reply

Your email address will not be published. Required fields are marked *