Problem Brief

Find Least Possible Vulnerability

FULLTIMEOA

See Amazon online assessment and hiring insights

Note 📝 - Another problem related to find server vulnerability Find Kth Minimum Vulnerability 🐹

A great solution insight from a pro in the server. Hope it helps you solve this problem! 👇

Another pro in the server mentioned that this problem is similar to LC 1004. Hopefully, the similarity can help bring some insights for you. Happi Coding! You are not alone! 🫶

Developers at Amazon IAM are working on identifying vulnerabilities in their key generation process. The key is represented as an array of n integers, where the i-th integer is denoted by key[i]

The vulnerability factor of the array is defined as the maximum length of a contiguous subarray that has a Greatest Common Divisor (GCD) greater than 1.

You are allowed to make at most maxChange modifications to the array, where each modification consists of changing any one element in the array to any other integer.

Your task is to determine the least possible vulnerability factor of the key after performing at most maxChange modifications.

If no valid subarray has GCD > 1, the vulnerability factor is considered 0.

Function Description

Complete the function findLeastPossibleVulnerabilityFactor in the editor.

findLeastPossibleVulnerability has the following parameters:

1. int[] key: an array of integers
2. int maxChange: the maximum number of changes allowed

Returns

int: the least possible vulnerability factor of the array after performing at most maxChange modifications.

A heartfelt thank you to all the amazing friends who so generously offered their help in completing this question! 🌷

1Example 1

Input

key = [2, 2, 4, 9, 6], maxChange = 1

Output

Explanation

The inital vulnerability factor is 3 (subarray [2, 2, 4]). Possible modifications - Change key[0] to 3 --> [3, 2, 4, 9, 6] ---> max subarray length with GCD ----> 1 is 2 ([2, 4] and [9, 6]) Change key[2] to 5 --> [2, 2, 5, 9, 6] ---> max subarray length with GCD ----> 1 is 2 ([2, 2] and [9, 6]) The least vulnerability factor after at most 1 change is 2.

2Example 2

Input

key = [5, 10, 20, 10, 15, 5], maxChange = 2

Output

Explanation

A super huge thank you to the friend who helped verify the accuracy of this test case! :3 First Change - ~ Modify the third element of the array to 2 and the fourth element to 3, so the updated key becomes [5, 10, 2, 3, 15, 5] ~ In this case , the maximum length of a subarray with a GCD greater than 1 is 2. This applies to several subarrays: [5, 10], [10, 2], [3, 15], [15, 5] Second Change - ~ Modify the first element of the array to 7 and the fourth element to 9, so the updated key becomes [7, 10, 20, 9, 15, 5] ~ Here as well, the maximum length of a subarray with a GCD greater than 1 is 2, for the following subarrays: [10, 20], [15, 5] Thus, after making the changes, the least possible vulnerability factor of the key is 2. This official exlplanation was added on 06-17-2025 :) Relevant source image was included in Problem Source.

3Example 3

Input

key = [4, 2, 4], maxChange = 1

Output

Explanation

Currently, the array has a GCD of 2 and a length of 3, but the optimal length is 1. The only way to achieve the optimal length is to change the second element to a value a has a GCD of 1 with 4. For example, chyange the key to [4, 3, 4]. In this case, the subarray with a GCD greater tha n1 are: [4], [3], [4]. Since the maximum length of these subarrays is 1, the least possible vulnerability factor of the key is 1. This official explanation was added on 06-17-2025 :3 Relevant source image was included in Problem Source.

4Example 4

Input

key = [3, 5, 7, 11, 13], maxChange = 2

Output

Explanation

All numbers are prime, so no subarray has GCD > 1. If we change key[0] to 2 and key[1] to 4, we still can't form a valid subarray with GCD > 1. Thus, the minimum possible vulnerability factor is 0. This new test case was added on 03-28-2025.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10^5
0 <= maxChange <= n
1 <= key[i] <= 10^9