leetcode medium : Number of Subarrays With LCM Equal to K

https://leetcode.com/problems/number-of-subarrays-with-lcm-equal-to-k/

 

N이 1000정도라서 O(n^2) bruteforce가 가능하다. (n^3은 안됨)

각각의 subarray들을 일일이 검사할수있다는 뜻이다.

근데 나는 각 subarray들마다 lcm을 찾아야하니까 또 O(n)이 필요해서 O(n^3)인줄 알았는데

생각해보니 i를 고정시켜놓고 j를 증가시키는 과정에서 lcm을 업데이트하면서 k보다 같은지 큰지만 검사해주면된다.

lcm update는 O(1)이라는 소리. 그래서 총 O(n^2)으로 해결 가능하다. 코드를 보면 이해가 쉽다.

from math import lcm

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:

        answer = 0
        for i in range(len(nums)):
            listLcm = 1
            for j in range(i, len(nums)):
                listLcm = lcm(listLcm, nums[j])
                if listLcm == k:
                    answer += 1
                if listLcm > k:
                    break
        
        return answer

lcm이랑 gcd를 직접 구현해서 써봤더니 gcd에서 maximum recursion depth에러가 떠서 그냥 내장함수로 바꿨다. (lcm = a * b / gcd(a,b) )