Given an array of N integers and a number X, the task is to find the number of segments such that all elements in the segment are greater than X. The count should not include overlapping segments and two or more contiguous segments should be considered as one.
Examples:
Input: a[] = {3, 4, 5, 6, 7, 2, 10, 11}, X = 5
Output: 2
The two segments are {6, 7} and {10, 11}.Input: a[] = {8, 25, 10, 19, 19, 18, 20, 11, 18}, X = 13
Output: 3
The segments are {25}, {19, 19, 18, 20} and {18}
Approach: Initialize a flag counter as false, mark it true whenever any element greater than X occurs. Whenever any element is not greater than X, count the segment if the flag is true. Re-initialize flag to false whenever any element <=X appears.
Below is the implementation of the above approach.
C++
// C++ program to count the number of segments // in which all elements are greater than X #include <bits/stdc++.h> using namespace std; // Function to count number of segments int countSegments( int a[], int n, int x) { bool flag = false ; int count = 0; // Iterate in the array for ( int i = 0; i < n; i++) { // check if array element // greater than X or not if (a[i] > x) { flag = true ; } else { // if flag is true if (flag) count += 1; flag = false ; } } // After iteration complete // check for the last segment if (flag) count += 1; return count; } // Driver Code int main() { int a[] = { 8, 25, 10, 19, 19, 18, 20, 11, 18 }; int n = sizeof (a) / sizeof (a[0]); int x = 13; cout << countSegments(a, n, x); return 0; } |
Java
// Java program to count the number of segments // in which all elements are greater than X import java.io.*; class GFG { // Function to count number of segments static int countSegments( int a[], int n, int x) { boolean flag = false ; int count = 0 ; // Iterate in the array for ( int i = 0 ; i < n; i++) { // check if array element // greater than X or not if (a[i] > x) { flag = true ; } else { // if flag is true if (flag) count += 1 ; flag = false ; } } // After iteration complete // check for the last segment if (flag) count += 1 ; return count; } // Driver Code public static void main (String[] args) { int a[] = { 8 , 25 , 10 , 19 , 19 , 18 , 20 , 11 , 18 }; int n =a.length; int x = 13 ; System.out.println(countSegments(a, n, x)); } } // This code is contributed by anuj_67.. |
Python3
# Python 3 program to count the number of segments # in which all elements are greater than X # Function to count number of segments def countSegments(a, n, x): flag = False count = 0 # Iterate in the array for i in range (n): # check if array element greater # than X or not if (a[i] > x): flag = True else : # if flag is true if (flag): count + = 1 flag = False # After iteration complete # check for the last segment if (flag): count + = 1 return count # Driver Code if __name__ = = '__main__' : a = [ 8 , 25 , 10 , 19 , 19 , 18 , 20 , 11 , 18 ] n = len (a) x = 13 print (countSegments(a, n, x)) # This code is contributed by # Sanjit_Prasad |
C#
// C# program to count the number of segments // in which all elements are greater than X using System; public class GFG{ // Function to count number of segments static int countSegments( int []a, int n, int x) { bool flag = false ; int count = 0; // Iterate in the array for ( int i = 0; i < n; i++) { // check if array element // greater than X or not if (a[i] > x) { flag = true ; } else { // if flag is true if (flag) count += 1; flag = false ; } } // After iteration complete // check for the last segment if (flag) count += 1; return count; } static public void Main (){ int []a = { 8, 25, 10, 19, 19, 18, 20, 11, 18 }; int n =a.Length; int x = 13; Console.WriteLine(countSegments(a, n, x)); } } |
Javascript
<script> // Javascript program to count // the number of segments // in which all elements // are greater than X // Function to count number of segments function countSegments(a, n, x) { let flag = false ; let count = 0; // Iterate in the array for (let i = 0; i < n; i++) { // check if array element // greater than X or not if (a[i] > x) { flag = true ; } else { // if flag is true if (flag) count += 1; flag = false ; } } // After iteration complete // check for the last segment if (flag) count += 1; return count; } let a = [ 8, 25, 10, 19, 19, 18, 20, 11, 18 ]; let n = a.length; let x = 13; document.write(countSegments(a, n, x)); </script> |
PHP
<?php // PHP program to count the number // of segments in which all elements // are greater than X // Function to count number of segments function countSegments( $a , $n , $x ) { $flag = false; $count = 0; // Iterate in the array for ( $i = 0; $i < $n ; $i ++) { // check if array element // greater than X or not if ( $a [ $i ] > $x ) { $flag = true; } else { // if flag is true if ( $flag ) $count += 1; $flag = false; } } // After iteration complete // check for the last segment if ( $flag ) $count += 1; return $count ; } // Driver Code $a = array ( 8, 25, 10, 19, 19, 18, 20, 11, 18 ); $n = sizeof( $a ); $x = 13; echo countSegments( $a , $n , $x ); // This code is contributed by ajit ?> |
3
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(1)
Approach : Sliding Window
Using sliding window technique. Maintain a window that expands from left to right as long as the elements in the window are
greater than X. Whenever we encounter an element that is not greater than X, we close the current window and move the left pointer
of the window to the next position. This way, we ensure that we count non-overlapping segments.
Steps:
- Initialize a variable count = 0 to keep track of the number of segments.
- Initialize two pointers, left=0 and right=0, both pointing to the start of the array.
- Iterate while right < N.
- If the element at right index > X, increment right.
- If the element at right index <= X, calculate the length of the current segment as length = right – left.
- If length is greater than 0, increment count.
- Move the left pointer to the next position (i.e., left = right + 1).
- Increment right.
- Return the count as the result.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <iostream> #include <vector> using namespace std; // Function to count the number of segments // with elements greater than X int countSegmentsGreaterThanX(std::vector< int >& arr, int X) { int count = 0; int left = 0, right = 0; int N = arr.size(); // Iterate until the right pointer reaches the end of // the array while (right < N) { if (arr[right] > X) { right++; } else { int length = right - left; if (length > 0) { count++; } // Move the left pointer to the next position left = right + 1; // Move the right pointer right++; } } // Check if there is a segment ending at the last // element int length = right - left; if (length > 0) { count++; } return count; } // Driver Code int main() { vector< int > arr = { 3, 4, 5, 6, 7, 2, 10, 11 }; int X = 5; int segments = countSegmentsGreaterThanX(arr, X); cout << segments << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class Main { // Function to count the number of segments // with elements greater than X static int countSegmentsGreaterThanX(List<Integer> arr, int X) { int count = 0 ; int left = 0 , right = 0 ; int N = arr.size(); // Iterate until the right pointer reaches the end of // the array while (right < N) { if (arr.get(right) > X) { right++; } else { int length = right - left; if (length > 0 ) { count++; } // Move the left pointer to the next position left = right + 1 ; // Move the right pointer right++; } } // Check if there is a segment ending at the last // element int length = right - left; if (length > 0 ) { count++; } return count; } // Driver Code public static void main(String[] args) { List<Integer> arr = new ArrayList<Integer>(); arr.add( 3 ); arr.add( 4 ); arr.add( 5 ); arr.add( 6 ); arr.add( 7 ); arr.add( 2 ); arr.add( 10 ); arr.add( 11 ); int X = 5 ; int segments = countSegmentsGreaterThanX(arr, X); System.out.println(segments); } } |
Python3
# Function to count the number of segments # with elements greater than X def countSegmentsGreaterThanX(arr, X): count = 0 left = 0 right = 0 N = len (arr) # Iterate until the right pointer reaches the end of the array while right < N: if arr[right] > X: right + = 1 else : length = right - left if length > 0 : count + = 1 # Move the left pointer to the next position left = right + 1 # Move the right pointer right + = 1 # Check if there is a segment ending at the last element length = right - left if length > 0 : count + = 1 return count # Driver Code arr = [ 3 , 4 , 5 , 6 , 7 , 2 , 10 , 11 ] X = 5 segments = countSegmentsGreaterThanX(arr, X) print (segments) |
C#
using System; using System.Collections.Generic; class Program { // Function to count the number of segments // with elements greater than X static int CountSegmentsGreaterThanX(List< int > arr, int X) { int count = 0; int left = 0, right = 0; int N = arr.Count; // Iterate until the right pointer reaches the end of // the list while (right < N) { if (arr[right] > X) { right++; } else { int length = right - left; if (length > 0) { count++; } // Move the left pointer to the next position left = right + 1; // Move the right pointer right++; } } // Check if there is a segment ending at the last // element int finalLength = right - left; if (finalLength > 0) { count++; } return count; } // Driver Code static void Main( string [] args) { List< int > arr = new List< int > { 3, 4, 5, 6, 7, 2, 10, 11 }; int X = 5; int segments = CountSegmentsGreaterThanX(arr, X); Console.WriteLine(segments); } } // This code is contributed by shivamgupta310570 |
Javascript
// Function to count the number of segments // with elements greater than X function countSegmentsGreaterThanX(arr, X) { let count = 0; let left = 0; let right = 0; const N = arr.length; // Iterate until the right pointer reaches the end of the array while (right < N) { if (arr[right] > X) { right++; } else { // Calculate the length of the current segment const length = right - left; if (length > 0) { count++; } // Move the left pointer to the next position left = right + 1; // Move the right pointer right++; } } // Check if there is a segment ending at the last element const length = right - left; if (length > 0) { count++; } return count; } // Driver Code const arr = [3, 4, 5, 6, 7, 2, 10, 11]; const X = 5; const segments = countSegmentsGreaterThanX(arr, X); console.log(segments); // This code is contributed by Kanchan Agarwal |
2
Time Complexity: O(N), where N is the size of the input array.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!