Given an array arr[], the task is to find the count of array elements satisfying the following conditions:
- The array elements should be strictly greater than all the previously occurring array elements.
- Either it is the last array element or the integer should be strictly larger than the next array element.
Note: The first integer of the array can also be considered.
Examples:
Input: arr[] = {1, 2, 0, 7, 2, 0, 2, 0}
Output: 2
Explanation: arr[1] (= 2) and arr[3] ( = 7) are the array elements satisfying the given condition.Input: arr[] = {4, 8, 15, 16, 23, 42}
Output: 1
Approach: The idea is to linearly traverse the array and check for each array element, if it satisfies the given condition or not. Follow the steps below to solve this problem:
- Traverse the array.
- Starting from the first element of the array, keep track of the maximum array element encountered so far.
- Update the maximum array element if it’s greater than the previous maximum array element encountered.
- After updating the current maximum, check if the next array element is greater than the current array element or not. If found to be true, increment the count.
- Repeat this process until the last array element is traversed.
- Finally, print the count obtained.
Below is the implementation for the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count array elements// satisfying the given conditionint numberOfIntegers(int arr[], int N){ int cur_max = 0, count = 0; // If there is only one // array element if (N == 1) { count = 1; } else { // Traverse the array for (int i = 0; i < N - 1; i++) { // Update the maximum element // encountered so far if (arr[i] > cur_max) { cur_max = arr[i]; // Count the number of array elements // strictly greater than all previous // and immediately next elements if (arr[i] > arr[i + 1]) { count++; } } } if (arr[N - 1] > cur_max) count++; } // Print the count cout << count;}// Driver Codeint main(){ // Given array int arr[] = { 1, 2, 0, 7, 2, 0, 2, 0 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); numberOfIntegers(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to count array elements // satisfying the given condition static void numberOfIntegers(int[] arr, int N) { int cur_max = 0, count = 0; // If there is only one // array element if (N == 1) { count = 1; } else { // Traverse the array for (int i = 0; i < N - 1; i++) { // Update the maximum element // encountered so far if (arr[i] > cur_max) { cur_max = arr[i]; // Count the number of array elements // strictly greater than all previous // and immediately next elements if (arr[i] > arr[i + 1]) { count++; } } } if (arr[N - 1] > cur_max) count++; } // Print the count System.out.println(count); } // Driver Code public static void main(String[] args) { // Given array int[] arr = new int[] { 1, 2, 0, 7, 2, 0, 2, 0 }; // Size of the array int N = arr.length; numberOfIntegers(arr, N); }}// This code is contributed by dharanendralv23 |
Python3
# Python program for the above approach# Function to count array elements# satisfying the given conditiondef numberOfIntegers(arr, N) : cur_max = 0 count = 0 # If there is only one # array element if (N == 1) : count = 1 else : # Traverse the array for i in range(N - 1): # Update the maximum element # encountered so far if (arr[i] > cur_max) : cur_max = arr[i] # Count the number of array elements # strictly greater than all previous # and immediately next elements if (arr[i] > arr[i + 1]) : count += 1 if (arr[N - 1] > cur_max) : count += 1 # Print the count print(count)# Driver Code# Given arrayarr = [ 1, 2, 0, 7, 2, 0, 2, 0 ]# Size of the arrayN = len(arr)numberOfIntegers(arr, N)# This code is contributed by sanjoy_62. |
C#
// C# program for the above approachusing System;class GFG { // Function to count array elements // satisfying the given condition static void numberOfIntegers(int[] arr, int N) { int cur_max = 0, count = 0; // If there is only one // array element if (N == 1) { count = 1; } else { // Traverse the array for (int i = 0; i < N - 1; i++) { // Update the maximum element // encountered so far if (arr[i] > cur_max) { cur_max = arr[i]; // Count the number of array elements // strictly greater than all previous // and immediately next elements if (arr[i] > arr[i + 1]) { count++; } } } if (arr[N - 1] > cur_max) count++; } // Print the count Console.WriteLine(count); } // Driver Code static public void Main() { // Given array int[] arr = new int[] { 1, 2, 0, 7, 2, 0, 2, 0 }; // Size of the array int N = arr.Length; numberOfIntegers(arr, N); }}// This code is contributed by dharavendralv23 |
Javascript
<script>// JavaScript implementation of the above approach // Function to count array elements // satisfying the given condition function numberOfIntegers(arr, N) { let cur_max = 0, count = 0; // If there is only one // array element if (N == 1) { count = 1; } else { // Traverse the array for (let i = 0; i < N - 1; i++) { // Update the maximum element // encountered so far if (arr[i] > cur_max) { cur_max = arr[i]; // Count the number of array elements // strictly greater than all previous // and immediately next elements if (arr[i] > arr[i + 1]) { count++; } } } if (arr[N - 1] > cur_max) count++; } // Print the count document.write(count); } // Driver code // Given array let arr = [ 1, 2, 0, 7, 2, 0, 2, 0 ]; // Size of the array let N = arr.length; numberOfIntegers(arr, N); </script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!