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)