Dada una array arr[] de N enteros positivos, la tarea es encontrar el recuento de índices i tal que todos los elementos desde arr[0] hasta arr[i – 1] sean más pequeños que arr[i] .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 4
Todos los índices cumplen la condición dada.
Entrada: arr[] = {4, 3, 2, 1}
Salida: 1
Solo i = 0 es el índice válido.
Enfoque: la idea es recorrer la array de izquierda a derecha y realizar un seguimiento del máximo actual, siempre que este máximo cambie, el índice actual es un índice válido, por lo tanto, incremente el contador resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count
// of indices that satisfy
// the given condition
int countIndices(int arr[], int n)
{
// To store the result
int cnt = 0;
// To store the current maximum
// Initialized to 0 since there are only
// positive elements in the array
int max = 0;
for (int i = 0; i < n; i++) {
// i is a valid index
if (max < arr[i]) {
// Update the maximum so far
max = arr[i];
// Increment the counter
cnt++;
}
}
return cnt;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(int);
cout << countIndices(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the count
// of indices that satisfy
// the given condition
static int countIndices(int arr[], int n)
{
// To store the result
int cnt = 0;
// To store the current maximum
// Initialized to 0 since there are only
// positive elements in the array
int max = 0;
for (int i = 0; i < n; i++)
{
// i is a valid index
if (max < arr[i])
{
// Update the maximum so far
max = arr[i];
// Increment the counter
cnt++;
}
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4 };
int n = arr.length;
System.out.println(countIndices(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of the approach # Function to return the count # of indices that satisfy # the given condition def countIndices(arr, n): # To store the result cnt = 0; # To store the current maximum # Initialized to 0 since there are only # positive elements in the array max = 0; for i in range(n): # i is a valid index if (max < arr[i]): # Update the maximum so far max = arr[i]; # Increment the counter cnt += 1; return cnt; # Driver code if __name__ == '__main__': arr = [ 1, 2, 3, 4 ]; n = len(arr); print(countIndices(arr, n)); # This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count
// of indices that satisfy
// the given condition
static int countIndices(int []arr, int n)
{
// To store the result
int cnt = 0;
// To store the current maximum
// Initialized to 0 since there are only
// positive elements in the array
int max = 0;
for (int i = 0; i < n; i++)
{
// i is a valid index
if (max < arr[i])
{
// Update the maximum so far
max = arr[i];
// Increment the counter
cnt++;
}
}
return cnt;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4 };
int n = arr.Length;
Console.WriteLine(countIndices(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript implementation of the approach
// Function to return the count
// of indices that satisfy
// the given condition
function countIndices(arr , n) {
// To store the result
var cnt = 0;
// To store the current maximum
// Initialized to 0 since there are only
// positive elements in the array
var max = 0;
for (i = 0; i < n; i++) {
// i is a valid index
if (max < arr[i]) {
// Update the maximum so far
max = arr[i];
// Increment the counter
cnt++;
}
}
return cnt;
}
// Driver code
var arr = [ 1, 2, 3, 4 ];
var n = arr.length;
document.write(countIndices(arr, n));
// This code contributed by aashish1995
</script>
Producción:
4
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)