Amazon Online Assessment: Minimum Vulnerability Factor Key Array Problem

Problem Description 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 d

Problem Description 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.

Example 1:

**Input**: key = [2, 2, 4, 9, 6], maxChange = 1 Output: 2

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.

Example 2:

**Input**: key = [5, 10, 20, 10, 15, 5], maxChange = 2 Output: 2

Example 3:

**Input**: key = [4, 2, 4], maxChange = 1 Output: 1

Example 4:

**Input**: key = [3, 5, 7, 11, 13], maxChange = 2 Output: 0

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