Dado un número entero N que denota la longitud de una array, la tarea es contar el número de subarreglo y subsecuencia posibles con la longitud dada de la array.
Ejemplos:
Entrada: N = 5
Salida:
Recuento de subarreglo = 15
Recuento de subsecuencia = 32
Entrada: N = 3
Salida:
Recuento de subarreglo = 6
Recuento de subsecuencia = 8
Enfoque: El hecho de observación clave para el conteo del subarreglo es el número de posiciones finales posibles para cada elemento índice del arreglo que puede ser (N – i). Por lo tanto, el conteo del subarreglo para un arreglo de tamaño N puede ser:
Count of Sub-arrays = (N) * (N + 1) --------------- 2
El hecho de observación clave para el recuento de la subsecuencia posible es que cada elemento de la array puede incluirse en una subsecuencia o no. Por lo tanto, la elección para cada elemento es 2.
Count of subsequences = 2N
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count // the subarray and subsequence of // given length of the array #include <bits/stdc++.h> using namespace std; // Function to count the subarray // for the given array int countSubarray(int n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length int countSubsequence(int n){ return pow(2, n); } // Driver Code int main() { int n = 5; cout << (countSubarray(n)) << endl; cout << (countSubsequence(n)) << endl; return 0; } // This code is contributed by mohit kumar 29
Java
// Java implementation to count // the subarray and subsequence of // given length of the array class GFG{ // Function to count the subarray // for the given array static int countSubarray(int n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length static int countSubsequence(int n){ return (int) Math.pow(2, n); } // Driver Code public static void main(String[] args) { int n = 5; System.out.print((countSubarray(n)) +"\n"); System.out.print((countSubsequence(n)) +"\n"); } } // This code is contributed by Princi Singh
Python
# Python implementation to count # the subarray and subsequence of # given length of the array # Function to count the subarray # for the given array def countSubarray(n): return ((n)*(n + 1))//2 # Function to count the subsequence # for the given array length def countSubsequence(n): return (2**n) # Driver Code if __name__ == "__main__": n = 5 print(countSubarray(n)) print(countSubsequence(n))
C#
// C# implementation to count // the subarray and subsequence of // given length of the array using System; class GFG{ // Function to count the subarray // for the given array static int countSubarray(int n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length static int countSubsequence(int n){ return (int) Math.Pow(2, n); } // Driver Code public static void Main(String[] args) { int n = 5; Console.Write((countSubarray(n)) +"\n"); Console.Write((countSubsequence(n)) +"\n"); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript implementation to count // the subarray and subsequence of // given length of the array // Function to count the subarray // for the given array function countSubarray(n){ return ((n)*(n + 1))/2; } // Function to count the subsequence // for the given array length function countSubsequence(n){ return Math.pow(2, n); } // Driver Code let n = 5; document.write((countSubarray(n)) +"<br/>"); document.write((countSubsequence(n)) +"\n"); </script>
15 32
Complejidad de tiempo: O (log n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por _mridul_bhardwaj_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA