Longest Subarray With at Most K Distinct Prime Factors - Video Solutions
Leetcode 4032 | Longest Subarray With at Most K Distinct Prime Factors | Leetcode weekly context 516
Longest Subarray With at Most K Distinct Prime Factors - Video Solution
Watch 4 video solutions for Longest Subarray With at Most K Distinct Prime Factors, a medium level problem. This walkthrough by CodeWithMeGuys has 157 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 1052 <= nums[i] <= 1051 <= k <= 104