Maximum distinct prime factors of elements in a K-length subarray

0 0 9 minutes read

Given an array arr[] of N positive integers and an integer K, the task is to find the maximum distinct prime factors in a subarray of length K.

Examples:

Input: arr[] = {5, 9, 14, 6, 10, 77}, K=3
Output: 5
Explanation:
The sub-array of length 3 with maximum distinct prime factors is 6, 10, 77 and prime factors are 2, 3, 5, 7, 11.

Input: arr[] = {4, 2, 6, 10}, K=3
Output: 3
Explanation:
The sub-array of length 3 with maximum distinct prime factors is 2, 6, 10 and prime factors are 2, 3, 5.

Naive Approach: The simplest approach is to generate all possible subarrays of length K and for traverse each subarray and count distinct prime factors of its elements. Finally, print the maximum count of distinct prime factors obtained for any subarray. Time complexity: O(N² log N)
Auxiliary Space: O(N)

Efficient Approach: The idea is to use the Sliding Window Technique to solve this problem. Follow the steps below:

Generate and store the smallest prime factor of every element using Sieve.
Store the distinct prime factors of first K array elements in a Map.
Traverse the remaining array maintaining the K-length window by adding current element to the previous subarray and removing the first element of the previous subarray
Find all the prime factors of the newly added element to the subarray and store it in the Map. Subtract the frequency of prime factors of the removed element from the Map.
After completing the above operations for the entire array, print the maximum Map size obtained for any subarray as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define Max 100001
 
// Stores smallest prime
// factor for every number
int spf[Max];
 
// Function to calculate smallest
// prime factor of every number
void sieve()
{
    // Marking smallest prime factor
    // of every number to itself
    for (int i = 1; i < Max; i++)
        spf[i] = i;
 
    // Separately marking smallest prime
    // factor of every even number to be 2
    for (int i = 4; i < Max; i = i + 2)
        spf[i] = 2;
 
    for (int i = 3; i * i < Max; i++)
 
        // If i is prime
        if (spf[i] == i) {
 
            // Mark spf for all numbers divisible by i
            for (int j = i * i; j < Max; j = j + i) {
 
                // Marking spf[j] if it is not
                // previously marked
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
}
 
// Function to find maximum distinct
// prime factors of subarray of length k
int maximumDPF(int arr[], int n, int k)
{
    // Precalculate Smallest
    // Prime Factors
    sieve();
 
    int ans = 0, num;
 
    // Stores distinct prime factors
    // for subarrays of size k
    unordered_map<int, int> maps;
 
    // Calculate total prime factors
    // for first k array elements
    for (int i = 0; i < k; i++) {
 
        // Calculate prime factors of
        // every element in O(logn)
        num = arr[i];
        while (num != 1) {
 
            maps[spf[num]]++;
            num = num / spf[num];
        }
    }
 
    // Update maximum distinct
    // prime factors obtained
    ans = max((int)maps.size(), ans);
 
    for (int i = k; i < n; i++) {
 
        // Remove prime factors of
        // the removed element
        num = arr[i - k];
        while (num != 1) {
 
            // Reduce frequencies
            // of prime factors
            maps[spf[num]]--;
 
            if (maps[spf[num]] == 0)
 
                // Erase that index from map
                maps.erase(spf[num]);
 
            num = num / spf[num];
        }
 
        // Find prime factoes of
        // added element
        num = arr[i];
        while (num != 1) {
 
            // Increase frequencies
            // of prime factors
            maps[spf[num]]++;
            num = num / spf[num];
        }
 
        // Update maximum distinct
        // prime factors obtained
        ans = max((int)maps.size(), ans);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 2, 6, 10 };
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << maximumDPF(arr, n, k) << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    static int Max = 100001;
    static int spf[] = new int[Max];
 
    // Function to precalculate smallest
    // prime factor of every number
    public static void sieve()
    {
        // Marking smallest prime factor
        // of every number to itself.
        for (int i = 1; i < Max; i++)
            spf[i] = i;
 
        // Separately marking smallest prime
        // factor of every even number to be 2
        for (int i = 4; i < Max; i = i + 2)
            spf[i] = 2;
 
        for (int i = 3; i * i < Max; i++)
 
            // If i is prime
            if (spf[i] == i) {
 
                // Mark spf for all numbers divisible by i
                for (int j = i * i; j < Max; j = j + i) {
 
                    // Marking spf[j] if it is not
                    // previously marked
                    if (spf[j] == j)
                        spf[j] = i;
                }
            }
    }
 
    // Function to find maximum distinct
    // prime factors of subarray of length k
    public static int maximumDPF(int arr[], int n, int k)
    {
        // Precalculate smallest
        // prime factor
        sieve();
 
        int ans = 0, num;
 
        // Stores distinct prime factors
        // for subarrays of size k
        Map<Integer, Integer> maps
            = new HashMap<Integer, Integer>();
 
        // Calculate total prime factors
        // for first k array elements
        for (int i = 0; i < k; i++) {
 
            // Calculate prime factors of
            // every element in O(logn)
            num = arr[i];
            while (num != 1) {
 
                maps.put(spf[num],
                         maps.getOrDefault(spf[num], 0)
                             + 1);
                num = num / spf[num];
            }
        }
 
        // Update maximum distinct
        // prime factors obtained
        ans = Math.max((int)maps.size(), ans);
 
        for (int i = k; i < n; i++) {
 
            // Remove prime factors of
            // the removed element
            num = arr[i - k];
            while (num != 1) {
 
                // Reduce frequencies
                // of prime factors
                maps.put(spf[num],
                         maps.getOrDefault(spf[num], 0)
                             - 1);
 
                if (maps.get(spf[num]) == 0)
                    maps.remove(spf[num]);
 
                num = num / spf[num];
            }
 
            // Insert prime factors of
            // the added element
            num = arr[i];
            while (num != 1) {
 
                // Increase frequencies
                // of prime factors
                maps.put(spf[num],
                         maps.getOrDefault(spf[num], 0)
                             + 1);
                num = num / spf[num];
            }
 
            // Update maximum distinct
            // prime factors obtained
            ans = Math.max((int)maps.size(), ans);
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 4, 2, 6, 10 };
 
        int k = 3;
        int n = arr.length;
 
        System.out.println(maximumDPF(arr, n, k));
    }
}

Python3

# Python program for the above approach
import math as mt
 
Max = 100001
 
# Stores smallest prime factor for
# every number
spf = [0 for i in range(Max)]
 
# Function to precalculate smallest
# prime factor of every number
 
 
def sieve():
 
  # Marking smallest prime factor of every
    # number to itself.
    for i in range(1, Max):
        spf[i] = i
 
    # Separately marking spf for
    # every even number as 2
    for i in range(4, Max, 2):
        spf[i] = 2
 
    for i in range(3, mt.ceil(mt.sqrt(Max))):
 
        # Checking if i is prime
        if (spf[i] == i):
 
            # marking SPF for all numbers
            # divisible by i
            for j in range(i * i, Max, i):
 
                # marking spf[j] if it is
                # not previously marked
                if (spf[j] == j):
                    spf[j] = i
 
# Function to find maximum 
# distinct prime factors
# of the subarray of length k
 
 
def maximumDPF(arr, n, k):
 
    # precalculating Smallest Prime Factor
    sieve()
 
    ans = 0
 
    # map to store distinct prime factor
    # for subarray of size k
    maps = {}
 
    # Calculating the total prime factors
    # for first k elements
    for i in range(0, k):
 
        # Calculating prime factors of
        # every element in O(logn)
        num = arr[i]
        while num != 1:
            maps[spf[num]] = maps.get(
                             spf[num], 0)+1
            num = int(num / spf[num])
 
    ans = max(len(maps), ans)
 
    for i in range(k, n):
       
        # Perform operation for
        # removed element
        num = arr[i - k]
        while num != 1:
 
            maps[spf[num]] = maps.get(
                             spf[num], 0)-1
 
            # if value in map become 0,
            # then erase that index from map
            if maps.get(spf[num], 0) == 0:
                maps.pop(spf[num])
 
            num = int(num / spf[num])
 
        # Perform operation for
        # added element
        num = arr[i]
        while num != 1:
 
            maps[spf[num]] = int(maps.get(
                                 spf[num], 0))+1
            num = int(num / spf[num])
 
        ans = max(len(maps), ans)
 
    return ans
 
 
# Driver Code
if __name__ == '__main__':
 
    # Given array arr
    arr = [4, 2, 6, 10]
 
    # Given subarray size K
    k = 3
    n = len(arr)
 
    # Function call
    print(maximumDPF(arr, n, k))

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
    public static int Max = 100001;
 
    static int[] spf = new int[Max];
 
    // Function to precalculate smallest
    // prime factor of every number
    public static void sieve()
    {
        // Marking smallest prime factor
        // of every number to itself
        for (int i = 1; i < Max; i++)
            spf[i] = i;
 
        // Marking smallest prime factor
        // of every even number to be 2
        for (int i = 4; i < Max; i = i + 2)
            spf[i] = 2;
 
        for (int i = 3; i * i < Max; i++)
 
            // checking if i is prime
            if (spf[i] == i) {
 
                // Marking spf for all
                // numbers divisible by i
                for (int j = i * i; j < Max; j = j + i) {
 
                    // Marking spf[j] if it is not
                    // previously marked
                    if (spf[j] == j)
                        spf[j] = i;
                }
            }
    }
 
    // Function to find maximum
    // distinct prime factors
    // of the subarray of length k
    public static int maximumDPF(int[] arr,
                                 int n, int k)
    {
        // precalculating Smallest Prime Factor
        sieve();
 
        int ans = 0, num, currentCount;
 
        // Stores distinct prime factors
        // for subarrays of size k
        var maps = new Dictionary<int, int>();
 
        // Calculating the total prime factors
        // for first k array elements
        for (int i = 0; i < k; i++) {
 
            // Calculating prime factors of
            // every element in O(logn)
            num = arr[i];
            while (num != 1) {
 
                // Increase frequencies of
                // prime factors
                maps.TryGetValue(spf[num],
                                 out currentCount);
                maps[spf[num]] = currentCount + 1;
                num = num / spf[num];
            }
        }
 
        // Update maximum distinct
        // prime factors obtained
        ans = Math.Max(maps.Count, ans);
 
        for (int i = k; i < n; i++) {
 
            // Remove prime factors of
            // removed element
            num = arr[i - k];
            while (num != 1) {
 
                // Reduce frequencies
                // of prime factors
                maps.TryGetValue(spf[num],
                                 out currentCount);
                maps[spf[num]] = currentCount - 1;
 
                if (maps[spf[num]] == 0)
 
                    // Erase that index from map
                    maps.Remove(spf[num]);
 
                num = num / spf[num];
            }
 
            // Insert prime factors
            // added element
            num = arr[i];
            while (num != 1) {
 
                // Increase frequencies
                // of prime factors
                maps.TryGetValue(spf[num],
                                 out currentCount);
                maps[spf[num]] = currentCount + 1;
                num = num / spf[num];
            }
 
            ans = Math.Max(maps.Count, ans);
        }
 
        // Update maximum distinct
        // prime factors obtained
        return ans;
    }
 
    // Driver code
    static public void Main()
    {
 
        // Given array arr[]
        int[] arr = { 4, 2, 6, 10 };
 
        // Given subarray size K
        int k = 3;
        int n = arr.Length;
 
        Console.Write(maximumDPF(arr, n, k));
    }
}

Javascript

<script>
    // JavaScript program for the above approach
     
    const Max = 100001
 
    // Stores smallest prime
    // factor for every number
    let spf = new Array(Max).fill(0);
 
    // Function to calculate smallest
    // prime factor of every number
    const sieve = () => {
     
        // Marking smallest prime factor
        // of every number to itself
        for (let i = 1; i < Max; i++)
            spf[i] = i;
 
        // Separately marking smallest prime
        // factor of every even number to be 2
        for (let i = 4; i < Max; i = i + 2)
            spf[i] = 2;
 
        for (let i = 3; i * i < Max; i++)
 
            // If i is prime
            if (spf[i] == i) {
 
                // Mark spf for all numbers divisible by i
                for (let j = i * i; j < Max; j = j + i) {
 
                    // Marking spf[j] if it is not
                    // previously marked
                    if (spf[j] == j)
                        spf[j] = i;
                }
            }
    }
 
    // Function to find maximum distinct
    // prime factors of subarray of length k
    const maximumDPF = (arr, n, k) => {
        // Precalculate Smallest
        // Prime Factors
        sieve();
 
        let ans = 0, num;
 
        // Stores distinct prime factors
        // for subarrays of size k
        let maps = {};
 
        // Calculate total prime factors
        // for first k array elements
        for (let i = 0; i < k; i++) {
 
            // Calculate prime factors of
            // every element in O(logn)
            num = arr[i];
            while (num != 1) {
 
                maps[spf[num]]++;
                num = parseInt(num / spf[num]);
            }
        }
 
        // Update maximum distinct
        // prime factors obtained
        ans = Math.max(Object.keys(maps).length, ans);
 
        for (let i = k; i < n; i++) {
 
            // Remove prime factors of
            // the removed element
            num = arr[i - k];
            while (num != 1) {
 
                // Reduce frequencies
                // of prime factors
                if (spf[num] in maps) maps[spf[num]]--;
 
                if (maps[spf[num]] == 0)
 
                    // Erase that index from map
                    delete maps[spf[num]];
 
                num = parseInt(num / spf[num]);
            }
 
            // Find prime factoes of
            // added element
            num = arr[i];
            while (num != 1) {
 
                // Increase frequencies
                // of prime factors
                maps[spf[num]] = spf[num] in maps ? maps[spf[num]] + 1 : 1;
                num = parseInt(num / spf[num]);
            }
 
            // Update maximum distinct
            // prime factors obtained
            ans = Math.max(Object.keys(maps).length, ans);
        }
 
        return ans;
    }
 
    // Driver Code
 
    let arr = [4, 2, 6, 10];
    let k = 3;
    let n = arr.length;
 
    document.write(maximumDPF(arr, n, k));
 
// This code is contributed by rakeshsahni
 
</script>

Output:

Time Complexity: O(N * log N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!