Número máximo de números de Armstrong presentes en un subarreglo de tamaño K

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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *