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

0 0 8 minutes read

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 i^th element is 1 if it is a Perfect Number. Otherwise, the i^th 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:
1. Initialize a variable sum to store the sum of divisors.
2. 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.
3. 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 not
int 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 K
int 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 array
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 : 0;
    }
 
    return maxSum(arr, N, K);
}
 
// Driver Code
int 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 approach
import java.util.*;
class GFG{
 
// Function to check a number
// is Perfect Number or not
static 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 K
static 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 array
static 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 Code
public 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 not
def 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 K
def 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 array
def 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 Code
if __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 approach
using System;
class GFG{
 
// Function to check a number
// is Perfect Number or not
static 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 K
static 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 array
static 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 Code
public 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 not
function 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 K
function 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 array
function 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 Code
let 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:

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