Find Least Possible Vulnerability
Updated
Problem statement
Developers at Amazon IAM represent an encryption key as an integer array key. Its vulnerability factor is the maximum length of a non-empty contiguous subarray whose greatest common divisor (GCD) is greater than 1.
You may modify at most maxChange array elements, replacing each selected value with any other integer. Return the least vulnerability factor that can be achieved.
A one-element subarray containing x > 1 has GCD x and therefore counts. The vulnerability factor is 0 only when no non-empty subarray has GCD greater than 1; for example, this happens when every array element is 1.
Function
findVulnerabilityFactor(key: int[], maxChange: int) → intExamples
Example 1
key = [2, 2, 4, 9, 6]maxChange = 1return = 2The original vulnerability factor is 3, from [2,2,4]. Changing the first value to 3 breaks that run, but the length-2 subarrays [2,4] and [9,6] still have GCD greater than 1. One change cannot break both, so the minimum is 2.
Example 2
key = [5, 10, 20, 10, 15, 5]maxChange = 2return = 2Changing the third and fourth values to 2 and 3 gives [5,10,2,3,15,5]. Its longest qualifying subarrays have length 2, including [5,10], [10,2], [3,15], and [15,5]. No two changes can eliminate every qualifying length-2 subarray, so the minimum is 2.
Example 3
key = [4, 2, 4]maxChange = 1return = 1Change the middle value to 3, producing [4,3,4]. Every adjacent pair then has GCD 1, while each value by itself still has GCD greater than 1. Therefore the minimum vulnerability factor is 1.
Example 4
key = [3, 5, 7, 11, 13]maxChange = 2return = 1Every adjacent pair already has GCD 1, so the current vulnerability factor is 1. It cannot become 0 with only two changes: at least three primes remain greater than 1, and each remaining prime forms a qualifying one-element subarray. Therefore the minimum is 1.
Constraints
1 ≤ n == key.length ≤ 1050 ≤ maxChange ≤ n1 ≤ key[i] ≤ 109
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Sliding Window MedianAuxoAI · OA
- Fastest Average Speed over a Rolling KilometerOptiver · OAOptiver interview questions
- Find Array Uniqueness Median 🐈Microsoft · OAMicrosoft interview questions
- Linear InterpolatorTwo Sigma · OATwo Sigma interview questions
- Sliding-Window Means with IEEE Special ValuesHeadlands Technologies · OAHeadlands Technologies interview questions
- Rock JumpingIMC Trading · OAIMC Trading interview questions
- Floor Square Roots for an ArrayWells Fargo · OAWells Fargo interview questions
- TikTok Video Relevance AdjustmentTikTok · OATikTok interview questions
- Maximum Visible DronesAnduril · PHONE SCREENAnduril interview questions
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences