Dada una array arr[] que consiste en N enteros positivos, la tarea es contar subarreglos que consisten solo en elementos de un solo dígito.
Ejemplos:
Entrada: arr[] = {0, 1, 14, 2, 5}
Salida: 6
Explicación: Todos los subarreglos hechos de números de un solo dígito son {{0}, {1}, {2}, {5}, {0 , 1}, {2, 5}}. Por lo tanto, el recuento total de subarreglos es 6.Entrada: arr[] ={12, 5, 14, 17}
Salida: 1
Explicación: Todos los subarreglos formados por números de un solo dígito son {5}.
Por lo tanto, el recuento total de subarreglos es 1.
Enfoque ingenuo: el enfoque más simple es recorrer el arreglo y generar todos los subarreglos posibles . Para cada subarreglo, verifique si todos los números enteros en él son números enteros de un solo dígito o no.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar el tamaño de cada bloque de enteros contiguos de un solo dígito e incrementar el conteo en subarreglos totales de esa longitud. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res = 0 y c = 0 , para almacenar el recuento total de subarreglos y el recuento total de enteros de un solo dígito en un subarreglo.
- Recorra la array y realice las siguientes operaciones:
- Si arr[i] < 10, incremente la cuenta de c en uno y la cuenta de res en c.
- De lo contrario, asigne c = 0.
- Finalmente, imprima el recuento total de subarreglos enteros de un solo dígito.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count of subarrays made
// up of single digit integers only
int singleDigitSubarrayCount(int arr[],
int N)
{
// Stores count of subarrays
int res = 0;
// Stores the count of consecutive
// single digit numbers in the array
int count = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
if (arr[i] <= 9) {
// Increment size of block by 1
count++;
// Increment res by count
res += count;
}
else {
// Assign count = 0
count = 0;
}
}
cout << res;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 0, 1, 14, 2, 5 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
singleDigitSubarrayCount(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to count of subarrays made
// up of single digit integers only
static void singleDigitSubarrayCount(int arr[],
int N)
{
// Stores count of subarrays
int res = 0;
// Stores the count of consecutive
// single digit numbers in the array
int count = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
if (arr[i] <= 9)
{
// Increment size of block by 1
count++;
// Increment res by count
res += count;
}
else
{
// Assign count = 0
count = 0;
}
}
System.out.print(res);
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 0, 1, 14, 2, 5 };
// Size of the array
int N = arr.length;
singleDigitSubarrayCount(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to count of subarrays made # up of single digit integers only def singleDigitSubarrayCount(arr, N): # Stores count of subarrays res = 0 # Stores the count of consecutive # single digit numbers in the array count = 0 # Traverse the array for i in range(N): if (arr[i] <= 9): # Increment size of block by 1 count += 1 # Increment res by count res += count else: # Assign count = 0 count = 0 print (res) # Driver Code if __name__ == '__main__': # Given array arr = [0, 1, 14, 2, 5] # Size of the array N = len(arr) singleDigitSubarrayCount(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
// Function to count of subarrays made
// up of single digit integers only
static void singleDigitSubarrayCount(int[] arr,
int N)
{
// Stores count of subarrays
int res = 0;
// Stores the count of consecutive
// single digit numbers in the array
int count = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
if (arr[i] <= 9)
{
// Increment size of block by 1
count++;
// Increment res by count
res += count;
}
else
{
// Assign count = 0
count = 0;
}
}
Console.Write(res);
}
// Driver Code
public static void Main(string[] args)
{
// Given array
int[] arr = { 0, 1, 14, 2, 5 };
// Size of the array
int N = arr.Length;
singleDigitSubarrayCount(arr, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to count of subarrays made
// up of single digit integers only
function singleDigitSubarrayCount(arr, N)
{
// Stores count of subarrays
let res = 0;
// Stores the count of consecutive
// single digit numbers in the array
let count = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
if (arr[i] <= 9)
{
// Increment size of block by 1
count++;
// Increment res by count
res += count;
}
else
{
// Assign count = 0
count = 0;
}
}
document.write(res);
}
// Driver Code
// Given array
let arr = [ 0, 1, 14, 2, 5 ];
// Size of the array
let N = arr.length;
singleDigitSubarrayCount(arr, N);
// This code is contributed by Manoj.
</script>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA