6

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

 2 years ago
source link: https://www.geeksforgeeks.org/maximum-number-of-armstrong-numbers-present-in-a-subarray-of-size-k/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

  • Difficulty Level : Medium
  • Last Updated : 08 Sep, 2021

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:

  • Python3
  • Javascript
// 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;
}
Output: 
4

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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK