Dado un arreglo de N enteros y un número K, la tarea es encontrar el número de subarreglos tales que todos los elementos sean mayores que K en él.
Ejemplos:
Entrada : a[] = {3, 4, 5, 6, 7, 2, 10, 11}, K = 5
Salida : 6
Los posibles subarreglos son {6}, {7}, {6, 7}, {10 }, {11} y {10, 11}.
Entrada : a[] = {8, 25, 10, 19, 19, 18, 20, 11, 18}, K = 13
Salida : 12
Enfoque: La idea es comenzar a recorrer la array usando un contador. Si el elemento actual es mayor que el valor dado X, incremente el contador; de lo contrario, agregue contador*(contador+1)/2 al número de subarreglos y reinicie el contador a 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the number of subarrays such
// that all elements are greater than K
#include <bits/stdc++.h>
using namespace std;
// Function to count number of subarrays
int countSubarrays(int a[], int n, int x)
{
int count = 0;
int number = 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) {
count += 1;
}
else {
number += (count) * (count + 1) / 2;
count = 0;
}
}
// After iteration complete
// check for the last set of subarrays
if (count)
number += (count) * (count + 1) / 2;
return number;
}
// Driver Code
int main()
{
int a[] = { 3, 4, 5, 6, 7, 2, 10, 11 };
int n = sizeof(a) / sizeof(a[0]);
int k = 5;
cout << countSubarrays(a, n, k);
return 0;
}
Java
// Java program to print the number of subarrays such
// that all elements are greater than K
import java.io.*;
class GFG {
// Function to count number of subarrays
static int countSubarrays(int a[], int n, int x)
{
int count = 0;
int number = 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) {
count += 1;
}
else {
number += (count) * (count + 1) / 2;
count = 0;
}
}
// After iteration complete
// check for the last set of subarrays
if (count!=0)
number += (count) * (count + 1) / 2;
return number;
}
// Driver Code
public static void main (String[] args) {
int a[] = { 3, 4, 5, 6, 7, 2, 10, 11 };
int n = a.length;
int k = 5;
System.out.println (countSubarrays(a, n, k));
}
}
Python3
# Python program to print the number of # subarrays such that all elements are # greater than K # Function to count number of subarrays def countSubarrays(a, n, x): count = 0 number = 0 # Iterate in the array for i in range(n): # check if array element greater # then X or not if (a[i] > x): count += 1 else: number += (count) * (count + 1) / 2 count = 0 # After iteration complete check for # the last set of subarrays if (count): number += (count) * (count + 1) / 2 return int(number) # Driver Code if __name__ == '__main__': a = [3, 4, 5, 6, 7, 2, 10, 11] n = len(a) k = 5 print(countSubarrays(a, n, k)) # This code is contributed by 29AjayKumar
C#
// C# program to print the number of subarrays such
// that all elements are greater than K
using System;
class GFG {
// Function to count number of subarrays
static int countSubarrays(int []a, int n, int x)
{
int count = 0;
int number = 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) {
count += 1;
}
else {
number += (count) * (count + 1) / 2;
count = 0;
}
}
// After iteration complete
// check for the last set of subarrays
if (count!=0)
number += (count) * (count + 1) / 2;
return number;
}
// Driver Code
public static void Main () {
int []a = { 3, 4, 5, 6, 7, 2, 10, 11 };
int n = a.Length;
int k = 5;
Console.WriteLine(countSubarrays(a, n, k));
}
}
// This code is contributed by anuj_67..
PHP
<?php
// PHP program to print the number
// of subarrays such that all
// elements are greater than K
// Function to count number
// of subarrays
function countSubarrays($a, $n, $x)
{
$count = 0; $number = 0;
// Iterate in the array
for ($i = 0; $i < $n; $i++)
{
// check if array element
// greater than X or not
if ($a[$i] > $x)
{
$count += 1;
}
else
{
$number += ($count) *
($count + 1) / 2;
$count = 0;
}
}
// After iteration complete
// check for the last set
// of subarrays
if ($count)
$number += ($count) *
($count + 1) / 2;
return $number;
}
// Driver Code
$a = array(3, 4, 5, 6, 7, 2, 10, 11);
$n = count($a);
$k = 5;
echo countSubarrays($a, $n, $k);
// This code is contributed by anuj_67
?>
Javascript
<script>
// javascript program to print the number of subarrays such
// that all elements are greater than K
// Function to count number of subarrays
function countSubarrays(a , n , x) {
var count = 0;
var number = 0;
// Iterate in the array
for (i = 0; i < n; i++) {
// check if array element
// greater than X or not
if (a[i] > x) {
count += 1;
} else {
number += (count) * (count + 1) / 2;
count = 0;
}
}
// After iteration complete
// check for the last set of subarrays
if (count != 0)
number += (count) * (count + 1) / 2;
return number;
}
// Driver Code
var a = [ 3, 4, 5, 6, 7, 2, 10, 11 ];
var n = a.length;
var k = 5;
document.write(countSubarrays(a, n, k));
// This code is contributed by todaysgaurav
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array