fork download
copy 
  1. from math import gcd
  2. from collections import defaultdict
  3.  
  4. def findVulnerabilityFactor(key, maxChange):
  5.     from math import gcd
  6.     from functools import lru_cache
  7.  
  8.     n = len(key)
  9.  
  10.     # Helper: Compute GCD of subarray from l to r
  11.     def subarray_gcd(arr):
  12.         g = arr[0]
  13.         for num in arr[1:]:
  14.             g = gcd(g, num)
  15.             if g == 1:
  16.                 return 1
  17.         return g
  18.  
  19.     # Check if it's possible to make all subarrays of length > L have GCD == 1
  20.     def is_valid(L):
  21.         for i in range(n):
  22.             g = 0
  23.             cnt = 0
  24.             for j in range(i, n):
  25.                 g = gcd(g, key[j])
  26.                 if g == 1:
  27.                     break
  28.                 cnt += 1
  29.                 if cnt > L:
  30.                     # Try to break it with at most maxChange changes
  31.                     # Try changing elements to 1 inside window [i..j]
  32.                     # Count how many need to be changed to make GCD 1
  33.                     change_needed = 0
  34.                     for k in range(i, j + 1):
  35.                         if key[k] % g == 0:
  36.                             change_needed += 1
  37.                     if change_needed <= maxChange:
  38.                         continue
  39.                     else:
  40.                         return False
  41.         return True
  42.  
  43.     # Binary search on the minimum vulnerability factor
  44.     left, right = 0, n
  45.     answer = n
  46.     while left <= right:
  47.         mid = (left + right) // 2
  48.         if is_valid(mid):
  49.             answer = mid
  50.             right = mid - 1
  51.         else:
  52.             left = mid + 1
  53.     return answer
  54.  
  55. def main():
  56.     # Test Case 1
  57.     key1 = [2, 2, 4, 9, 6]
  58.     maxChange1 = 1
  59.     result1 = findVulnerabilityFactor(key1, maxChange1)
  60.     print(f"Test Case 1: Vulnerability Factor = {result1}")  # Expected: 2
  61.  
  62.     # Test Case 2
  63.     key2 = [5, 10, 20, 10, 15, 5]
  64.     maxChange2 = 2
  65.     result2 = findVulnerabilityFactor(key2, maxChange2)
  66.     print(f"Test Case 2: Vulnerability Factor = {result2}")  # Expected: 2
  67.  
  68. if __name__ == "__main__":
  69.     main()
Success #stdin #stdout 0.1s 14116KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test Case 1: Vulnerability Factor = 3
Test Case 2: Vulnerability Factor = 6
https://ideone.com/yHyNvR
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!