Dado un arreglo arr[] de enteros, nuestra tarea es encontrar la longitud del subarreglo más grande tal que todos los elementos del subarreglo sean Número autobiográfico.
Un número autobiográfico es un número tal que el primer dígito cuenta cuántos ceros hay en él, el segundo dígito cuenta cuántos hay y así sucesivamente.
Por ejemplo, 21200 tiene 2 cero, 1 uno, 2 dos y 0 tres y 0 cuatro.
Ejemplos:
Entrada: arr[]={21200, 1, 1303, 1210, 2020}
Salida: 2
Explicación:
La longitud máxima del subarreglo con todos los números como Número autobiográfico es {1210, 2020}.
Entrada: arr[]={100, 200, 300, 400, 1200, 500}
Salida: 0
Explicación:
Ninguno de ellos es Número autobiográfico.
Enfoque:
Para resolver el problema mencionado anteriormente, debemos seguir los pasos que se detallan a continuación:
- Recorra la array desde el índice 0 e inicialice una variable max_length y current_length con 0.
- Si el elemento actual es un número autobiográfico, incremente la variable longitud_actual y continúe; de lo contrario, establezca longitud_actual en 0.
- En cada paso, asigne max_length como max_length = max(current_length, max_length). El valor final de max_length almacenará el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of the
// largest subarray whose every element is an
// Autobiographical Number
#include <bits/stdc++.h>
using namespace std;
// function to check number is autobiographical
bool isAutoBiographyNum(int number)
{
int count = 0, position, size, digit;
string NUM;
// Convert integer to string
NUM = to_string(number);
size = NUM.length();
// Iterate for every digit to check
// for their total count
for (int i = 0; i < size; i++) {
position = NUM[i] - '0';
count = 0;
// Check occurrence of every number
// and count them
for (int j = 0; j < size; j++) {
digit = NUM[j] - '0';
if (digit == i)
count++;
}
// Check if any position mismatches with
// total count them return with false
// else continue with loop
if (position != count)
return false;
}
return true;
}
// Function to return the length of the
// largest subarray whose every
// element is a Autobiographical number
int checkArray(int arr[], int n)
{
int current_length = 0;
int max_length = 0;
// Utility function which checks every element
// of array for Autobiographical number
for (int i = 0; i < n; i++) {
// Check if element arr[i] is an
// Autobiographical number
if (isAutoBiographyNum(arr[i]))
// Increment the current length
current_length++;
else
current_length = 0;
// Update max_length value
max_length = max(max_length, current_length);
}
// Return the final result
return max_length;
}
// Driver code
int main()
{
int arr[] = { 21200, 1, 1303, 1210, 2020 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << checkArray(arr, n) << "\n";
return 0;
}
Java
// Java program to find the length of the
// largest subarray whose every element is
// an autobiographical number
class GFG {
// Function to check number is autobiographical
static boolean isAutoBiographyNum(int number)
{
int count = 0, position, size, digit;
String NUM;
// Convert integer to string
NUM = Integer.toString(number);
size = NUM.length();
// Iterate for every digit to check
// for their total count
for(int i = 0; i < size; i++)
{
position = NUM.charAt(i) - '0';
count = 0;
// Check occurrence of every number
// and count them
for(int j = 0; j < size; j++)
{
digit = NUM.charAt(j) - '0';
if (digit == i)
count++;
}
// Check if any position mismatches with
// total count them return with false
// else continue with loop
if (position != count)
return false;
}
return true;
}
// Function to return the length of the
// largest subarray whose every
// element is a Autobiographical number
static int checkArray(int arr[], int n)
{
int current_length = 0;
int max_length = 0;
// Utility function which checks every element
// of array for autobiographical number
for(int i = 0; i < n; i++)
{
// Check if element arr[i] is an
// autobiographical number
if (isAutoBiographyNum(arr[i]) == true)
{
// Increment the current length
current_length++;
}
else
{
current_length = 0;
}
// Update max_length value
max_length = Math.max(max_length, current_length);
}
// Return the final result
return max_length;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 21200, 1, 1303, 1210, 2020 };
int n = arr.length;
System.out.println(checkArray(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find the length of the
# largest subarray whose every element is an
# autobiographical number
# Function to check number is autobiographical
def isAutoBiographyNum(number):
count = 0;
# Convert integer to string
NUM = str(number);
size = len(NUM);
# Iterate for every digit to check
# for their total count
for i in range(size):
position = ord(NUM[i]) - ord('0');
count = 0;
# Check occurrence of every number
# and count them
for j in range(size):
digit = ord(NUM[j]) - ord('0');
if (digit == i):
count += 1;
# Check if any position mismatches with
# total count them return with false
# else continue with loop
if (position != count):
return False;
return True;
# Function to return the length of the
# largest subarray whose every
# element is a autobiographical number
def checkArray(arr, n):
current_length = 0;
max_length = 0;
# Utility function which checks every element
# of array for autobiographical number
for i in range(n):
# Check if element arr[i] is an
# autobiographical number
if (isAutoBiographyNum(arr[i])):
# Increment the current length
current_length += 1;
else:
current_length = 0;
# Update max_length value
max_length = max(max_length,
current_length);
# Return the final result
return max_length;
# Driver code
if __name__ == "__main__":
arr = [ 21200, 1, 1303, 1210, 2020 ];
n = len(arr);
print(checkArray(arr, n));
# This code is contributed by AnkitRai01
C#
// C# program to find the length of the
// largest subarray whose every element
// is an autobiographical number
using System;
class GFG {
// Function to check number is autobiographical
static bool isAutoBiographyNum(int number)
{
int count = 0, position, size, digit;
string NUM;
// Convert integer to string
NUM = number.ToString();
size = NUM.Length;
// Iterate for every digit to check
// for their total count
for(int i = 0; i < size; i++)
{
position = NUM[i] - '0';
count = 0;
// Check occurrence of every number
// and count them
for(int j = 0; j < size; j++)
{
digit = NUM[j] - '0';
if (digit == i)
count++;
}
// Check if any position mismatches
// with total count them return with
// false else continue with loop
if (position != count)
return false;
}
return true;
}
// Function to return the length of the
// largest subarray whose every element
// is a autobiographical number
static int checkArray(int []arr, int n)
{
int current_length = 0;
int max_length = 0;
// Utility function which checks every element
// of array for autobiographical number
for(int i = 0; i < n; i++)
{
// Check if element arr[i] is an
// autobiographical number
if (isAutoBiographyNum(arr[i]) == true)
{
// Increment the current length
current_length++;
}
else
{
current_length = 0;
}
// Update max_length value
max_length = Math.Max(max_length,
current_length);
}
// Return the final result
return max_length;
}
// Driver code
public static void Main (string[] args)
{
int []arr = { 21200, 1, 1303, 1210, 2020 };
int n = arr.Length;
Console.WriteLine(checkArray(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript program to find the length of the
// largest subarray whose every element is an
// Autobiographical Number
// function to check number is autobiographical
function isAutoBiographyNum(number)
{
let count = 0, position, size, digit;
let NUM;
// Convert integer to string
NUM = number.toString();
size = NUM.length;
// Iterate for every digit to check
// for their total count
for (let i = 0; i < size; i++) {
position = NUM[i].charCodeAt() - '0'.charCodeAt();
count = 0;
// Check occurrence of every number
// and count them
for (let j = 0; j < size; j++) {
digit = NUM[j].charCodeAt() - '0'.charCodeAt();
if (digit == i)
count++;
}
// Check if any position mismatches with
// total count them return with false
// else continue with loop
if (position != count)
return false;
}
return true;
}
// Function to return the length of the
// largest subarray whose every
// element is a Autobiographical number
function checkArray(arr, n)
{
let current_length = 0;
let max_length = 0;
// Utility function which checks every element
// of array for Autobiographical number
for (let i = 0; i < n; i++) {
// Check if element arr[i] is an
// Autobiographical number
if (isAutoBiographyNum(arr[i]))
// Increment the current length
current_length++;
else
current_length = 0;
// Update max_length value
max_length = Math.max(max_length, current_length);
}
// Return the final result
return max_length;
}
let arr = [ 21200, 1, 1303, 1210, 2020 ];
let n = arr.length;
document.write(checkArray(arr, n));
</script>
Producción:
2
Complejidad de tiempo: O(n * log n)
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA