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 digitsint 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 notint 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 Kint 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 arrayint 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 Codeint 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 approachimport 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 digitsstatic 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 notstatic 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 Kstatic 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 arraystatic 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 Codepublic 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 digitsdef 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 notdef 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 Kdef 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 arraydef 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 Codeif __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 approachusing 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 digitsstatic 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 notstatic 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 Kstatic 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 arraystatic 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 Codepublic 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 digitsfunction 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 notfunction 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 Kfunction 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 arrayfunction 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 Codelet 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:
4
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/maximum-number-of-armstrong-numbers-present-in-a-subarray-of-size-k/ […]
… [Trackback]
[…] Read More on on that Topic: geeksforgeeks.org/maximum-number-of-armstrong-numbers-present-in-a-subarray-of-size-k/ […]