Given an array arr[ ] consisting of N integers, the task is to determine the maximum number of perfect Numbers in any subarray of size K.
Examples:
Input: arr[ ] = {28, 2, 3, 6, 496, 99, 8128, 24}, K = 4
Output: 3
Explanation: The sub-array {6, 496, 99, 8128} has 3 perfect numbers which is maximum.Input: arr[ ]= {1, 2, 3, 6}, K=2
Output: 1
Naive Approach: The approach is to generate all possible subarrays of size K and for each subarray, count the number of elements that are a Perfect Number. Print the maximum count obtained for any subarray.
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above approach, convert the given array arr[ ] into a binary array where the ith element is 1 if it is a Perfect Number. Otherwise, the ith element is 0. Therefore, the problem reduces to finding the maximum sum subarray of size K in the binary array using the Sliding Window technique. Follow the steps below to solve the problem:
- Traverse the array and for each element of the array arr[], check if it is a Perfect Number or not.
- If arr[i] is a Perfect Number then convert arr[i] equal to 1. Otherwise, convert arr[i] equal to 0.
- To check if a number is a perfect number or not:
- Initialize a variable sum to store the sum of divisors.
- Traverse every number in the range [1, arr[i] – 1] and check if it is a divisor of arr[i] or not. Add all the divisors.
- If the sum of all the divisors is equal to arr[i], then the number is a perfect number. Otherwise, the number is not a Perfect Number.
- Compute the sum of the first subarray of size K in the modified array.
- Using the sliding window technique, find the maximum sum of a subarray from all possible subarrays 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 check a number// is Perfect Number or notint isPerfect(int N){ // Stores sum of divisors int sum = 1; // Find all divisors and add them for (int i = 2; i < sqrt(N); i++) { if (N % i == 0) { if (i == N / i) { sum += i; } else { sum += i + N / i; } } } // If sum of divisors // is equal to N if (sum == N && N != 1) return 1; return 0;}// Function to return maximum// sum of a subarray of size Kint maxSum(int arr[], int N, int K){ // If k is greater than N if (N < K) { cout << "Invalid"; return -1; } // Compute sum of first window of size K int res = 0; for (int i = 0; i < K; i++) { res += arr[i]; } // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window 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 answer return res;}// Function to find all the// perfect numbers in the arrayint max_PerfectNumbers(int arr[], int N, int K){ // The given array is converted into binary array for (int i = 0; i < N; i++) { arr[i] = isPerfect(arr[i]) ? 1 : 0; } return maxSum(arr, N, K);}// Driver Codeint main(){ int arr[] = { 28, 2, 3, 6, 496, 99, 8128, 24 }; int K = 4; int N = sizeof(arr) / sizeof(arr[0]); cout << max_PerfectNumbers(arr, N, K); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{// Function to check a number// is Perfect Number or notstatic int isPerfect(int N){ // Stores sum of divisors int sum = 1; // Find all divisors and // add them for (int i = 2; i < Math.sqrt(N); i++) { if (N % i == 0) { if (i == N / i) { sum += i; } else { sum += i + N / i; } } } // If sum of divisors // is equal to N if (sum == N && N != 1) return 1; return 0;}// Function to return 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) { System.out.print("Invalid"); return -1; } // Compute sum of first // window of size K int res = 0; for (int i = 0; i < K; i++) { res += arr[i]; } // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window 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 answer return res;}// Function to find all the// perfect numbers in the arraystatic int max_PerfectNumbers(int arr[], int N, int K){ // The given array is converted // into binary array for (int i = 0; i < N; i++) { arr[i] = isPerfect(arr[i]) == 1 ? 1 : 0; } return maxSum(arr, N, K);}// Driver Codepublic static void main(String[] args){ int arr[] = {28, 2, 3, 6, 496, 99, 8128, 24}; int K = 4; int N = arr.length; System.out.print(max_PerfectNumbers(arr, N, K));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to check a number# is Perfect Number or notdef isPerfect(N): # Stores sum of divisors sum = 1 # Find all divisors and add them for i in range(2, N): if i * i > N: break if (N % i == 0): if (i == N // i): sum += i else: sum += i + N // i # If sum of divisors # is equal to N if (sum == N and N != 1): return 1 return 0# Function to return maximum# sum of a subarray of size Kdef maxSum(arr, N, K): # If k is greater than N if (N < K): print("Invalid") return -1 # Compute sum of first # window of size K res = 0 for i in range(K): res += arr[i] # Compute sums of remaining windows by # removing first element of previous # window and adding last element of # current window curr_sum = res for i in range(K, N): curr_sum += arr[i] - arr[i - K] res = max(res, curr_sum) # print(res) # Return the answer return res# Function to find all the# perfect numbers in the arraydef max_PerfectNumbers(arr, N, K): # The given array is converted # into binary array for i in range(N): if isPerfect(arr[i]): arr[i] = 1 else: arr[i] = 0 return maxSum(arr, N, K)# Driver Codeif __name__ == '__main__': arr = [ 28, 2, 3, 6, 496, 99, 8128, 24 ] K = 4 N = len(arr) print(max_PerfectNumbers(arr, N, K)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;class GFG{// Function to check a number// is Perfect Number or notstatic int isPerfect(int N){ // Stores sum of divisors int sum = 1; // Find all divisors and // add them for (int i = 2; i < Math.Sqrt(N); i++) { if (N % i == 0) { if (i == N / i) { sum += i; } else { sum += i + N / i; } } } // If sum of divisors // is equal to N if (sum == N && N != 1) return 1; return 0;}// Function to return 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) { Console.Write("Invalid"); return -1; } // Compute sum of first // window of size K int res = 0; for (int i = 0; i < K; i++) { res += arr[i]; } // Compute sums of remaining // windows by removing first // element of previous window // and adding last element of // current window 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 answer return res;}// Function to find all the// perfect numbers in the arraystatic int max_PerfectNumbers(int []arr, int N, int K){ // The given array is converted // into binary array for (int i = 0; i < N; i++) { arr[i] = isPerfect(arr[i]) == 1 ? 1 : 0; } return maxSum(arr, N, K);}// Driver Codepublic static void Main(String[] args){ int []arr = {28, 2, 3, 6, 496, 99, 8128, 24}; int K = 4; int N = arr.Length; Console.Write(max_PerfectNumbers(arr, N, K));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// Function to check a number// is Perfect Number or notfunction isPerfect(N){ // Stores sum of divisors let sum = 1; // Find all divisors and // add them for(let i = 2; i < Math.sqrt(N); i++) { if (N % i == 0) { if (i == N / i) { sum += i; } else { sum += i + N / i; } } } // If sum of divisors // is equal to N if (sum == N && N != 1) return 1; return 0;} // Function to return maximum// sum of a subarray of size Kfunction maxSum(arr, N, K){ // If k is greater than N if (N < K) { document.write("Invalid"); return -1; } // Compute sum of first // window of size K let res = 0; for(let i = 0; i < K; i++) { res += arr[i]; } // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window 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 answer return res;} // Function to find all the// perfect numbers in the arrayfunction max_PerfectNumbers(arr, N, K){ // The given array is converted // into binary array for(let i = 0; i < N; i++) { arr[i] = isPerfect(arr[i]) == 1 ? 1 : 0; } return maxSum(arr, N, K);}// Driver Codelet arr = [ 28, 2, 3, 6, 496, 99, 8128, 24 ];let K = 4;let N = arr.length;document.write(max_PerfectNumbers(arr, N, K));// This code is contributed by target_2 </script> |
Output:
3
Time Complexity: O( N * sqrt(N) )
Auxiliary Space: O(1)
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!
