Maximum number of Armstrong Numbers present in a subarray of size K

0 0 10 minutes read

Given an array arr[] consisting of N integers and a positive integer K, the task is to find the maximum count of Armstrong Numbers present in any subarray of size K.

Examples:

Input: arr[] = {28, 2, 3, 6, 153, 99, 828, 24}, K = 6
Output: 4
Explanation: The subarray {2, 3, 6, 153} contains only of Armstrong Numbers. Therefore, the count is 4, which is maximum possible.

Input: arr[] = {1, 2, 3, 6}, K = 2
Output: 2

Naive Approach: The simplest approach to solve the given problem is to generate all possible subarrays of size K and for each subarray, count the numbers that are an Armstrong Number. After checking for all the subarrays, print the maximum count obtained.

Time Complexity: O(N*K)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by changing each array element to 1 if it is an Armstrong Number, Otherwise, changing the array elements to 0 and then find the maximum sum subarray of size K in the updated array. Follow the steps below for the efficient approach:

Traverse the array arr[] and if the current element arr[i] is an Armstrong Number, then replace the current element with 1. Otherwise, replace it with 0.
After completing the above step, print the maximum sum of a subarray of size K as the maximum count of Armstrong Number in a subarray of size K.

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(N * d), where d is the maximum number of digits in any array element.
Auxiliary Space: O(N)

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 zambiatek!