Last Updated on March 23, 2022 by Ria Pathak
CONCEPTS USED:
Searching
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT(SIMPLIFIED):
Given an array
Aof 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 8SOLVING APPROACH:
The idea is to traverse the array from left to right and keep incrementing the
countwhenever we find thetallestbuilding of the array up till now.Initialise
tallestas-1andcountas0.Traverse the array and if an element is greater than
tallestthen update it astallestand incrementcountby1.Finally, print the value of
count.
ILLUSTRATION:
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)
[forminator_quiz id="1104"]
This article tried to discuss Searching. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.