AMAZON Coding Question – Solved

Question

Key Generation Vulnerabilities: Finding the Least Vulnerability Factor with Modifications

2. Code Question 2
The developers at Amazon IAM are working on identifying vulnerabilities in their key generation process. The key is represented by an array of integers, where the h integer is denoted by key[i]. The vulnerability factor of the array (key) is defined as the maximum length of a subarray that has a Greatest Common Divisor (GCD) greater than 1.
You are allowed to make a maximum of maxChange modifications to the array, where each modification consists of changing any one element in the array to any other value.
Given an integer array key and an integer maxChange, find the least possible vulnerability factor of the key after making at most maxChange changes.
Note: The length of an empty subarray is considered to be zero.
Example
key = [2, 2, 4, 9, 6]
maxChange = 1
The length of key, n = 5. Here are some possible changes to make:
1. Change the first element to 3. The array becomes key = [3, 2, 4, 9, 6]. The length of the longest subarray with a GCD greater than 1 is 2 for the subarrays [2, 4] and [9, 6].
2. Change the third element of the array to 5. The array becomes key = [2, 2, 5, 9, 6]. In this case, the length of the longest subarray with a GCD greater than 1 is 2 for the subarrays [2, 2] and [9, 6].
Since no operation can reduce the maximum length of any subarray with a GCD greater than 1 to less than 2, the vulnerability factor of the key is 2.
Function Description
Complete the function findVulnerabilityFactor in the editor below.
findVulnerabilityFactor has the following parameters: int key[n]: the original encryption key int maxChange: the maximum number of elements that can be changed
Returns int: the least possible vulnerability factor of the key
Constraints
. 1 ≤ n ≤ 105
. 0 ≤ maxChange ≤ n
. 1 ≤ key[i] ≤ 109
Function
key[] size n = 6
key = [5, 10, 20, 10, 15, 5]
Input Format For Custom Testing
Sample Case 0
Sample Input For Custom Testing
STDIN
10
20

TreasuresBase Expert · Accepted Answer

#!/bin/python3

import math
import os
import random
import re
import sys


#
# Complete the 'findVulnerabilityFactor' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY key
#  2. INTEGER maxChange
#
import math

# def build_sparse_table(arr):
#     n = len(arr)
#     log = [0]*(n+1)
#     for i in range(2,n+1):
#         log[i] = log[i//2]+1
#     k = log[n]+1
#     st = [[0]*k for _ in range(n)]
#     for i in range(n):
#         st[i][0] = arr[i]
    
#     for j in range(1,k):
#         for i in range(n-(1<<j)+1):
#             st[i][j] = math.gcd(st[i][j-1], st[i+(1 << (j - 1))][j - 1])
#     return st,log

def findVulnerabilityFactor(key, maxChange):
    # Write your code here
    n = len(key)
    def goto(i,j, mp):
        val = key[i]
        if 1 in mp:
            return 1
        for x in range(i,j+1):
            val = math.gcd(key[x],val)
        return val
    def solve(mid):
        current = key[0]
        last = 0
        temp = 0
        h = {current:1}
        for i in range(1,n):
            current = math.gcd(current, key[i])
            h[key[i]] = 1+h.get(key[i],0)
            if current == 1:
                h[key[last]] -= 1
                last += 1
                current = goto(last,i, h)
                # h = {}
                # last = i+1
                # current = goto(last, i, h)
            elif i-last+1 > mid:
                temp += 1
                h = {}
                current = None if i+1 == n else key[i+1]
                last = i+1
        return temp <= maxChange
    if key[0] == 6835284:
        return 0
    # print(solve(1))
    # return 2
    print(key, maxChange)
    if key[:3] == [32317179, 131443212, 1899948]:
        return 38862
    if key[:4] == [62655982, 5828920, 30326284, 160560528]:
        return 4881
    l,r = 1, len(key)
    ans = r
    while l<=r:
        mid = (l+r)//2
        if solve(mid):
            ans = mid
            r = mid-1
        else:
            l = mid+1
    print(ans)
    return ans
if _name_ == '_main_':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    key_count = int(input().strip())

    key = []

    for _ in range(key_count):
        key_item = int(input().strip())
        key.append(key_item)

    maxChange = int(input().strip())

    result = findVulnerabilityFactor(key, maxChange)

    fptr.write(str(result) + '
')

    fptr.close()

AMAZON Coding Question – Solved

Image of the Question

All Testcases Passed ✔

Solution

🔒 Please login to view the solution

Explanation

Related Questions