Dada una array arr[] que consta de N enteros y un entero positivo K , la tarea es encontrar el recuento máximo de números de Armstrong presentes en cualquier subarreglo de tamaño K .
Ejemplos:
Entrada: arr[] = {28, 2, 3, 6, 153, 99, 828, 24}, K = 6 Salida: 4
Explicación :
El subarreglo {2, 3, 6, 153} contiene solo números de Armstrong. Por lo tanto, la cuenta es 4, que es el máximo posible.Entrada: arr[] = {1, 2, 3, 6}, K = 2
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles de tamaño K y, para cada subarreglo, contar los números que son un número de Armstrong . Después de verificar todos los subarreglos, imprima el conteo máximo obtenido.
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar cambiando cada elemento de la array a 1 si es un número de Armstrong ; de lo contrario, cambie los elementos de la array a 0 y luego busque la suma máxima de subarreglo de tamaño K en la array actualizada. Siga los pasos a continuación para el enfoque eficiente:
- Recorra la array arr[] y, si el elemento actual arr[i] es un número de Armstrong, reemplace el elemento actual con 1 . De lo contrario, reemplácelo con 0 .
- Después de completar el paso anterior, imprima la suma máxima de un subarreglo de tamaño K como el recuento máximo del número de Armstrong en un subarreglo de tamaño K.
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 calculate the value of // x raised to the power y in O(log y) int power(int x, unsigned int y) { // Base Case if (y == 0) return 1; // If the power y is even if (y % 2 == 0) return power(x, y / 2) * power(x, y / 2); // Otherwise return x * power(x, y / 2) * power(x, y / 2); } // Function to calculate the order of // the number, i.e. count of digits int order(int num) { // Stores the total count of digits int count = 0; // Iterate until num is 0 while (num) { count++; num = num / 10; } return count; } // Function to check a number is // an Armstrong Number or not int isArmstrong(int N) { // Find the order of the number int r = order(N); int temp = N, sum = 0; // Check for Armstrong Number while (temp) { int d = temp % 10; sum += power(d, r); temp = temp / 10; } // If Armstrong number // condition is satisfied return (sum == N); } // Utility function to find the maximum // sum of a subarray of size K int maxSum(int arr[], int N, int K) { // If k is greater than N if (N < K) { return -1; } // Find the sum of first // subarray of size K int res = 0; for (int i = 0; i < K; i++) { res += arr[i]; } // Find the sum of the // remaining subarray int curr_sum = res; for (int i = K; i < N; i++) { curr_sum += arr[i] - arr[i - K]; res = max(res, curr_sum); } // Return the maximum sum // of subarray of size K return res; } // Function to find all the // Armstrong Numbers in the array int maxArmstrong(int arr[], int N, int K) { // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is an Armstrong // Number, then replace it by // 1. Otherwise, 0 arr[i] = isArmstrong(arr[i]); } // Return the resultant count return maxSum(arr, N, K); } // Driver Code int main() { int arr[] = { 28, 2, 3, 6, 153, 99, 828, 24 }; int K = 6; int N = sizeof(arr) / sizeof(arr[0]); cout << maxArmstrong(arr, N, K); return 0; }
Java
// Java program for above approach import java.util.*; class GFG{ // Function to calculate the value of // x raised to the power y in O(log y) static int power(int x, int y) { // Base Case if (y == 0) return 1; // If the power y is even if (y % 2 == 0) return power(x, y / 2) * power(x, y / 2); // Otherwise return x * power(x, y / 2) * power(x, y / 2); } // Function to calculate the order of // the number, i.e. count of digits static int order(int num) { // Stores the total count of digits int count = 0; // Iterate until num is 0 while (num > 0) { count++; num = num / 10; } return count; } // Function to check a number is // an Armstrong Number or not static int isArmstrong(int N) { // Find the order of the number int r = order(N); int temp = N, sum = 0; // Check for Armstrong Number while (temp > 0) { int d = temp % 10; sum += power(d, r); temp = temp / 10; } // If Armstrong number // condition is satisfied if (sum == N) return 1; return 0; } // Utility function to find the maximum // sum of a subarray of size K static int maxSum(int[] arr, int N, int K) { // If k is greater than N if (N < K) { return -1; } // Find the sum of first // subarray of size K int res = 0; for(int i = 0; i < K; i++) { res += arr[i]; } // Find the sum of the // remaining subarray int curr_sum = res; for(int i = K; i < N; i++) { curr_sum += arr[i] - arr[i - K]; res = Math.max(res, curr_sum); } // Return the maximum sum // of subarray of size K return res; } // Function to find all the // Armstrong Numbers in the array static int maxArmstrong(int[] arr, int N, int K) { // Traverse the array arr[] for(int i = 0; i < N; i++) { // If arr[i] is an Armstrong // Number, then replace it by // 1. Otherwise, 0 arr[i] = isArmstrong(arr[i]); } // Return the resultant count return maxSum(arr, N, K); } // Driver Code public static void main(String[] args) { int[] arr = { 28, 2, 3, 6, 153, 99, 828, 24 }; int K = 6; int N = arr.length; System.out.println(maxArmstrong(arr, N, K)); } } // This code is contributed by hritikrommie.
Python3
# Python 3 program for the above approach # Function to calculate the value of # x raised to the power y in O(log y) def power(x, y): # Base Case if (y == 0): return 1 # If the power y is even if (y % 2 == 0): return power(x, y // 2) * power(x, y // 2) # Otherwise return x * power(x, y // 2) * power(x, y // 2) # Function to calculate the order of # the number, i.e. count of digits def order(num): # Stores the total count of digits count = 0 # Iterate until num is 0 while (num): count += 1 num = num // 10 return count # Function to check a number is # an Armstrong Number or not def isArmstrong(N): # Find the order of the number r = order(N) temp = N sum = 0 # Check for Armstrong Number while (temp): d = temp % 10 sum += power(d, r) temp = temp // 10 # If Armstrong number # condition is satisfied return (sum == N) # Utility function to find the maximum # sum of a subarray of size K def maxSum(arr, N, K): # If k is greater than N if (N < K): return -1 # Find the sum of first # subarray of size K res = 0 for i in range(K): res += arr[i] # Find the sum of the # remaining subarray curr_sum = res for i in range(K,N,1): curr_sum += arr[i] - arr[i - K] res = max(res, curr_sum) # Return the maximum sum # of subarray of size K return res # Function to find all the # Armstrong Numbers in the array def maxArmstrong(arr, N, K): # Traverse the array arr[] for i in range(N): # If arr[i] is an Armstrong # Number, then replace it by # 1. Otherwise, 0 arr[i] = isArmstrong(arr[i]) # Return the resultant count return maxSum(arr, N, K) # Driver Code if __name__ == '__main__': arr = [28, 2, 3, 6, 153,99, 828, 24] K = 6 N = len(arr) print(maxArmstrong(arr, N, K)) # This code is contributed by ipg2016107.
C#
// C# program for above approach using System; class GFG{ // Function to calculate the value of // x raised to the power y in O(log y) static int power(int x, int y) { // Base Case if (y == 0) return 1; // If the power y is even if (y % 2 == 0) return power(x, y / 2) * power(x, y / 2); // Otherwise return x * power(x, y / 2) * power(x, y / 2); } // Function to calculate the order of // the number, i.e. count of digits static int order(int num) { // Stores the total count of digits int count = 0; // Iterate until num is 0 while (num > 0) { count++; num = num / 10; } return count; } // Function to check a number is // an Armstrong Number or not static int isArmstrong(int N) { // Find the order of the number int r = order(N); int temp = N, sum = 0; // Check for Armstrong Number while (temp > 0) { int d = temp % 10; sum += power(d, r); temp = temp / 10; } // If Armstrong number // condition is satisfied if (sum == N) return 1; return 0; } // Utility function to find the maximum // sum of a subarray of size K static int maxSum(int[] arr, int N, int K) { // If k is greater than N if (N < K) { return -1; } // Find the sum of first // subarray of size K int res = 0; for(int i = 0; i < K; i++) { res += arr[i]; } // Find the sum of the // remaining subarray int curr_sum = res; for(int i = K; i < N; i++) { curr_sum += arr[i] - arr[i - K]; res = Math.Max(res, curr_sum); } // Return the maximum sum // of subarray of size K return res; } // Function to find all the // Armstrong Numbers in the array static int maxArmstrong(int[] arr, int N, int K) { // Traverse the array arr[] for(int i = 0; i < N; i++) { // If arr[i] is an Armstrong // Number, then replace it by // 1. Otherwise, 0 arr[i] = isArmstrong(arr[i]); } // Return the resultant count return maxSum(arr, N, K); } // Driver Code public static void Main(String[] args) { int[] arr = { 28, 2, 3, 6, 153, 99, 828, 24 }; int K = 6; int N = arr.Length; Console.Write(maxArmstrong(arr, N, K)); } } // This code is contributed by shivanisinghss2110
Javascript
<script> // Javascript program for the above approach // Function to calculate the value of // x raised to the power y in O(log y) function power(x, y) { // Base Case if (y == 0) return 1; // If the power y is even if (y % 2 == 0) return power(x, Math.floor(y / 2)) * power(x, Math.floor(y / 2)); // Otherwise return x * power(x, Math.floor(y / 2)) * power(x, Math.floor(y / 2)); } // Function to calculate the order of // the number, i.e. count of digits function order(num) { // Stores the total count of digits let count = 0; // Iterate until num is 0 while (num) { count++; num = Math.floor(num / 10); } return count; } // Function to check a number is // an Armstrong Number or not function isArmstrong(N) { // Find the order of the number let r = order(N); let temp = N, sum = 0; // Check for Armstrong Number while (temp) { let d = temp % 10; sum += power(d, r); temp = Math.floor(temp / 10); } // If Armstrong number // condition is satisfied return sum == N; } // Utility function to find the maximum // sum of a subarray of size K function maxSum(arr, N, K) { // If k is greater than N if (N < K) { return -1; } // Find the sum of first // subarray of size K let res = 0; for(let i = 0; i < K; i++) { res += arr[i]; } // Find the sum of the // remaining subarray let curr_sum = res; for(let i = K; i < N; i++) { curr_sum += arr[i] - arr[i - K]; res = Math.max(res, curr_sum); } // Return the maximum sum // of subarray of size K return res; } // Function to find all the // Armstrong Numbers in the array function maxArmstrong(arr, N, K) { // Traverse the array arr[] for(let i = 0; i < N; i++) { // If arr[i] is an Armstrong // Number, then replace it by // 1. Otherwise, 0 arr[i] = isArmstrong(arr[i]); } // Return the resultant count return maxSum(arr, N, K); } // Driver Code let arr = [ 28, 2, 3, 6, 153, 99, 828, 24 ]; let K = 6; let N = arr.length; document.write(maxArmstrong(arr, N, K)); // This code is contributed by gfgking </script>
4
Complejidad de tiempo: O(N * d), donde d es el número máximo de dígitos en cualquier elemento de array.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saragupta1924 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA