Given an array of N elements. The task is to find the maximum number of the contiguous automorphic numbers in the given array.
Automorphic Numbers: A number is called Automorphic number if and only if its square ends in the same digits as the number itself.
For Example:
-> 76 is automorphic, since 76*76 = 5776(ends in 76) -> 5 is automorphic, since 5*5 = 25(ends in 5)
Examples:
Input : arr[] = {22, 6, 1, 625, 2, 1, 9376}
Output : 3
Input : arr[] = {99, 42, 31, 1, 5}
Output : 2
Approach:
- Traverse the array with two variables named current_max and max_so_far. Initialize both of them with 0.
- Check at each element if it is automorphic.
- Calculate the square of current number.
- Keep extracting and comparing digits from the end of both the current number and its square.
- If any mismatch is found, then the number is not automorphic.
- Otherwise if all of the digits from the current number is extracted without any mismatch, then the number is automorphic.
- If a automorphic number is found then increment current_max and compare it with max_so_far
- If current_max is greater than max_so_far, then assign max_so_far with current_max
- Every time a non automorphic element is found, reset current_max to 0.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to check Automorphic numberbool 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 numbersint 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, then 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 Codeint 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 approachclass GFG{ // Function to check Automorphic numberstatic 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 numbersstatic 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, then 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 Codepublic 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, then 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 approachusing System;class GFG{ // Function to check Automorphic numberstatic 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 numbersstatic 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, then 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 Codestatic 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 numberfunction 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 numbersfunction 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, then 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 numberfunction 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 numbersfunction 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, then 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 Codevar arr = [ 0, 3, 2, 5, 1, 9 ];var n = arr.length;document.write(maxAutomorphicSubarray(arr, n));// This code is contributed by rrrtnx</script> |
Output:
2
Time Complexity: O(n * log10m), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
