Dada una array de N elementos. La tarea es encontrar el número máximo de números automórficos contiguos en la array dada.
Números automórficos: un número se llama número automórfico si y solo si su cuadrado termina en los mismos dígitos que el número mismo.
Por ejemplo:
-> 76 is automorphic, since 76*76 = 5776(ends in 76) -> 5 is automorphic, since 5*5 = 25(ends in 5)
Ejemplos:
Input : arr[] = {22, 6, 1, 625, 2, 1, 9376}
Output : 3
Input : arr[] = {99, 42, 31, 1, 5}
Output : 2
Acercarse:
- Recorra la array con dos variables denominadas current_max y max_so_far. Inicialice ambos con 0.
- Comprueba en cada elemento si es automórfico.
- Calcular el cuadrado del número actual.
- Siga extrayendo y comparando dígitos desde el final del número actual y su cuadrado.
- Si se encuentra alguna discrepancia, entonces el número no es automórfico.
- De lo contrario, si todos los dígitos del número actual se extraen sin ninguna discrepancia, entonces el número es automórfico.
- Si se encuentra un número automórfico, incremente current_max y compárelo con max_so_far
- Si current_max es mayor que max_so_far, entonces asigne max_so_far con current_max
- Cada vez que se encuentre un elemento no automórfico, restablezca current_max a 0.
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 check Automorphic number
bool isAutomorphic(int N)
{
// Store the square
int sq = N * N;
// Start Comparing digits
while (N > 0) {
// Return false, if any digit of N doesn't
// match with its square's digits from last
if (N % 10 != sq % 10)
return false;
// Reduce N and square
N /= 10;
sq /= 10;
}
return true;
}
// Function to find the length of the maximum
// contiguous subarray of automorphic numbers
int maxAutomorphicSubarray(int arr[], int n)
{
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++) {
// check if element is non automorphic
if (isAutomorphic(arr[i]) == false)
current_max = 0;
// If element is automorphic, than update
// current_max and max_so_far accordingly.
else {
current_max++;
max_so_far = max(current_max, max_so_far);
}
}
return max_so_far;
}
// Driver Code
int main()
{
int arr[] = { 0, 3, 2, 5, 1, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxAutomorphicSubarray(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to check Automorphic number
static boolean isAutomorphic(int N)
{
// Store the square
int sq = N * N;
// Start Comparing digits
while (N > 0)
{
// Return false, if any digit of N doesn't
// match with its square's digits from last
if (N % 10 != sq % 10)
return false;
// Reduce N and square
N /= 10;
sq /= 10;
}
return true;
}
// Function to find the length of the maximum
// contiguous subarray of automorphic numbers
static int maxAutomorphicSubarray(int []arr, int n)
{
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++)
{
// check if element is non automorphic
if (isAutomorphic(arr[i]) == false)
current_max = 0;
// If element is automorphic, than update
// current_max and max_so_far accordingly.
else
{
current_max++;
max_so_far = Math.max(current_max,
max_so_far);
}
}
return max_so_far;
}
// Driver Code
public static void main(String[] args)
{
int []arr = { 0, 3, 2, 5, 1, 9 };
int n = arr.length;
System.out.println(maxAutomorphicSubarray(arr, n));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach # Function to check Automorphic number def isAutomorphic(N) : # Store the square sq = N * N; # Start Comparing digits while (N > 0) : # Return false, if any digit of N doesn't # match with its square's digits from last if (N % 10 != sq % 10) : return False; # Reduce N and square N //= 10; sq //= 10; return True; # Function to find the length of the maximum # contiguous subarray of automorphic numbers def maxAutomorphicSubarray(arr, n) : current_max = 0; max_so_far = 0; for i in range(n) : # check if element is non automorphic if (isAutomorphic(arr[i]) == False) : current_max = 0; # If element is automorphic, than update # current_max and max_so_far accordingly. else : current_max += 1; max_so_far = max(current_max, max_so_far); return max_so_far; # Driver Code if __name__ == "__main__" : arr = [ 0, 3, 2, 5, 1, 9 ]; n = len(arr) ; print(maxAutomorphicSubarray(arr, n)); # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to check Automorphic number
static bool isAutomorphic(int N)
{
// Store the square
int sq = N * N;
// Start Comparing digits
while (N > 0)
{
// Return false, if any digit of N doesn't
// match with its square's digits from last
if (N % 10 != sq % 10)
return false;
// Reduce N and square
N /= 10;
sq /= 10;
}
return true;
}
// Function to find the length of the maximum
// contiguous subarray of automorphic numbers
static int maxAutomorphicSubarray(int []arr, int n)
{
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++)
{
// check if element is non automorphic
if (isAutomorphic(arr[i]) == false)
current_max = 0;
// If element is automorphic, than update
// current_max and max_so_far accordingly.
else
{
current_max++;
max_so_far = Math.Max(current_max, max_so_far);
}
}
return max_so_far;
}
// Driver Code
static void Main()
{
int []arr = { 0, 3, 2, 5, 1, 9 };
int n = arr.Length;
Console.WriteLine(maxAutomorphicSubarray(arr, n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
// Function to check Automorphic number
function isAutomorphic($N)
{
// Store the square
$sq = $N * $N;
// Start Comparing digits
while ($N > 0)
{
// Return false, if any digit of N doesn't
// match with its square's digits from last
if ($N % 10 != $sq % 10)
return false;
// Reduce N and square
$N = (int)($N / 10);
$sq = (int)($sq / 10);
}
return true;
}
// Function to find the length of the maximum
// contiguous subarray of automorphic numbers
function maxAutomorphicSubarray($arr, $n)
{
$current_max = 0; $max_so_far = 0;
for ($i = 0; $i < $n; $i++)
{
// check if element is non automorphic
if (isAutomorphic($arr[$i]) == false)
$current_max = 0;
// If element is automorphic, than update
// current_max and max_so_far accordingly.
else
{
$current_max++;
$max_so_far = max($current_max,
$max_so_far);
}
}
return $max_so_far;
}
// Driver Code
$arr = array(0, 3, 2, 5, 1, 9 );
$n = sizeof($arr);
echo(maxAutomorphicSubarray($arr, $n));
// This code is contributed by Code_Mech.
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to check Automorphic number
function isAutomorphic(N)
{
// Store the square
var sq = N * N;
// Start Comparing digits
while (N > 0)
{
// Return false, if any digit of N doesn't
// match with its square's digits from last
if (N % 10 != sq % 10)
return false;
// Reduce N and square
N = parseInt(N / 10);
sq = parseInt(sq / 10);
}
return true;
}
// Function to find the length of the maximum
// contiguous subarray of automorphic numbers
function maxAutomorphicSubarray(arr, n)
{
var current_max = 0, max_so_far = 0;
for(var i = 0; i < n; i++)
{
// Check if element is non automorphic
if (isAutomorphic(arr[i]) == false)
current_max = 0;
// If element is automorphic, than update
// current_max and max_so_far accordingly.
else
{
current_max++;
max_so_far = Math.max(current_max,
max_so_far);
}
}
return max_so_far;
}
// Driver Code
var arr = [ 0, 3, 2, 5, 1, 9 ];
var n = arr.length;
document.write(maxAutomorphicSubarray(arr, n));
// This code is contributed by rrrtnx
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA