Welcome to Subscribe On Youtube

4032. Longest Subarray With at Most K Distinct Prime Factors

Description

You are given an integer array nums consisting of positive integers and an integer k.

The prime factor set of a subarray is the union of the distinct prime factors of all its elements.

Return the length of the longest subarray whose prime factor set contains at most k distinct prime factors. If no such subarray exists, return 0.

 

Example 1:

Input: nums = [7,6,10,12,11], k = 3

Output: 3

Explanation:

Consider the subarray [6, 10, 12]:

  • The distinct prime factors of 6 are {2, 3}.
  • The distinct prime factors of 10 are {2, 5}.
  • The distinct prime factors of 12 are {2, 3}.
  • The union of these sets is {2, 3, 5}, which contains 3 distinct prime factors.

No longer subarray satisfies the condition. Therefore, the answer is 3.

Example 2:

Input: nums = [4,6,9,18], k = 4

Output: 4

Explanation:

Consider the entire array [4, 6, 9, 18]:

  • The distinct prime factors of 4 are {2}.
  • The distinct prime factors of 6 are {2, 3}.
  • The distinct prime factors of 9 are {3}.
  • The distinct prime factors of 18 are {2, 3}.
  • The union of these sets is {2, 3}, which contains 2 distinct prime factors.

Since 2 <= 4, the entire array is valid. Therefore, the answer is 4.

Example 3:

Input: nums = [6,10,15], k = 2

Output: 1

Explanation:

Every subarray of length at least 2 has prime factor set {2, 3, 5}, which contains 3 distinct prime factors.

Since 3 > 2, only subarrays of length 1 are valid. Therefore, the answer is 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 2 <= nums[i] <= 105
  • 1 <= k <= 104

Solutions

Solution 1: Preprocessing + Sliding Window

Thinking

A subarray is legal if and only if it has at most $k$ distinct prime factors. That constraint is monotone in the window, so a sliding window applies.

Factoring every value online would multiply $n$ by $M=10^5$. A sieve stores the prime-factor lists on $[2,M]$; the window updates a hash table from those lists as it expands or shrinks.

Whenever the number of distinct primes is again at most $k$, the window length updates the answer.

First, we preprocess the list of prime factors for every number in $[2, 10^5]$ and store them in $\textit{primes}$. Specifically, we enumerate $i = 2, 3, \cdots, M$. If $\textit{primes}[i]$ is empty, then $i$ is a prime, and we add $i$ to the prime-factor list of every multiple of $i$.

Then we use a sliding window to find the longest valid subarray. A hash table $\textit{cnt}$ records the occurrence count of each prime factor in the current window. When the right pointer $r$ expands, we add all prime factors of $\textit{nums}[r]$ to the window. When the number of distinct prime factors in the window exceeds $k$, the left pointer $l$ shrinks and we remove the prime factors of $\textit{nums}[l]$. Whenever the window is valid, we update the answer with the window length.

The time complexity is $O(M \log \log M + n \log M)$, and the space complexity is $O(M \log \log M)$, where $n$ is the length of $\textit{nums}$ and $M = 10^5$ is the maximum value of the array elements.

  • class Solution {
    static final int MX = 100001;
    static List<Integer>[] primes = new ArrayList[MX];

    static {
        for (int i = 0; i < MX; i++) {
            primes[i] = new ArrayList<>();
        }

        for (int i = 2; i < MX; i++) {
            if (primes[i].isEmpty()) {
                for (int j = i; j < MX; j += i) {
                    primes[j].add(i);
                }
            }
        }
    }

    public int longestSubarray(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();

        int ans = 0;
        int l = 0;

        for (int r = 0; r < nums.length; r++) {
            for (int p : primes[nums[r]]) {
                cnt.merge(p, 1, Integer::sum);
            }

            while (cnt.size() > k) {
                for (int p : primes[nums[l]]) {
                    if (cnt.merge(p, -1, Integer::sum) == 0) {
                        cnt.remove(p);
                    }
                }
                l++;
            }

            ans = Math.max(ans, r - l + 1);
        }

        return ans;
    }
}

  • class Solution {
public:
    int longestSubarray(vector<int>& nums, int k) {
        const int MX = 100001;

        static vector<vector<int>> primes(MX);

        static bool initialized = false;
        if (!initialized) {
            initialized = true;

            for (int i = 2; i < MX; i++) {
                if (primes[i].empty()) {
                    for (int j = i; j < MX; j += i) {
                        primes[j].push_back(i);
                    }
                }
            }
        }

        unordered_map<int, int> cnt;

        int ans = 0;
        int l = 0;

        for (int r = 0; r < nums.size(); r++) {
            for (int p : primes[nums[r]]) {
                cnt[p]++;
            }

            while (cnt.size() > k) {
                for (int p : primes[nums[l]]) {
                    if (--cnt[p] == 0) {
                        cnt.erase(p);
                    }
                }
                l++;
            }

            ans = max(ans, r - l + 1);
        }

        return ans;
    }
};

  • mx = 100001
primes = [[] for _ in range(mx)]
for i in range(2, mx):
    if not primes[i]:
        for j in range(i, mx, i):
            primes[j].append(i)


class Solution:
    def longestSubarray(self, nums: list[int], k: int) -> int:
        cnt = defaultdict(int)
        ans = l = 0
        for r, x in enumerate(nums):
            for y in primes[x]:
                cnt[y] += 1
            while len(cnt) > k:
                for y in primes[nums[l]]:
                    cnt[y] -= 1
                    if cnt[y] == 0:
                        cnt.pop(y)
                l += 1
            ans = max(ans, r - l + 1)
        return ans


  • var primes [100001][]int

func init() {
	for i := 2; i < 100001; i++ {
		if len(primes[i]) == 0 {
			for j := i; j < 100001; j += i {
				primes[j] = append(primes[j], i)
			}
		}
	}
}

func longestSubarray(nums []int, k int) int {
	cnt := map[int]int{}

	ans := 0
	l := 0

	for r, x := range nums {

		for _, p := range primes[x] {
			cnt[p]++
		}

		for len(cnt) > k {
			for _, p := range primes[nums[l]] {
				cnt[p]--
				if cnt[p] == 0 {
					delete(cnt, p)
				}
			}
			l++
		}

		ans = max(ans, r-l+1)
	}

	return ans
}


  • const MX = 100001;

const primes: number[][] = Array.from({ length: MX }, () => []);

for (let i = 2; i < MX; i++) {
    if (primes[i].length === 0) {
        for (let j = i; j < MX; j += i) {
            primes[j].push(i);
        }
    }
}

function longestSubarray(nums: number[], k: number): number {
    const cnt = new Map<number, number>();

    let ans = 0;
    let l = 0;

    for (let r = 0; r < nums.length; r++) {
        for (const p of primes[nums[r]]) {
            cnt.set(p, (cnt.get(p) ?? 0) + 1);
        }

        while (cnt.size > k) {
            for (const p of primes[nums[l]]) {
                cnt.set(p, cnt.get(p)! - 1);

                if (cnt.get(p) === 0) {
                    cnt.delete(p);
                }
            }
            l++;
        }

        ans = Math.max(ans, r - l + 1);
    }

    return ans;
}


  • use std::collections::HashMap;
use std::sync::OnceLock;

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>, k: i32) -> i32 {
        static PRIMES: OnceLock<Vec<Vec<i32>>> = OnceLock::new();

        let primes = PRIMES.get_or_init(|| {
            let mut primes = vec![Vec::<i32>::new(); 100001];

            for i in 2..100001 {
                if primes[i].is_empty() {
                    let mut j = i;
                    while j < 100001 {
                        primes[j].push(i as i32);
                        j += i;
                    }
                }
            }

            primes
        });

        let mut cnt: HashMap<i32, i32> = HashMap::new();

        let mut ans = 0;
        let mut l = 0usize;

        for r in 0..nums.len() {
            for &p in &primes[nums[r] as usize] {
                *cnt.entry(p).or_insert(0) += 1;
            }

            while cnt.len() > k as usize {
                for &p in &primes[nums[l] as usize] {
                    let v = cnt.get_mut(&p).unwrap();
                    *v -= 1;

                    if *v == 0 {
                        cnt.remove(&p);
                    }
                }

                l += 1;
            }

            ans = ans.max(r as i32 - l as i32 + 1);
        }

        ans
    }
}

All Problems

All Solutions