How should I practice Find Least Possible Vulnerability?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Find Least Possible Vulnerability associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Array

Find Least Possible Vulnerability

Learn this problem

● HardAmazonFULLTIMEOA

See Amazon hiring insights

Problem statement

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

findLeastPossibleVulnerability(key: int[], maxChange: int) → int

Complete the function findLeastPossibleVulnerability in the editor below. It has the following parameters:

int[] key: the original encryption key array
int maxChange: the maximum number of elements that can be changed

Returns

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

Examples

Example 1

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

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.

Example 2

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

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.

Example 3

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

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.

Example 4

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

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

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