URL

Subarray Product Less Than K - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202403/subarray_product_less_than_k/main.fsx

let numSubarrayProductLessThanK (nums: int list) (k: int) : int =
    let rec moveLeft (nums: int[]) left right product =
        if left >= right || product < k then
            left, product
        else
            moveLeft nums (left + 1) right (product / nums.[left])

    let rec numSubarrayProductLessThanK' (nums: int[]) left right product acc =
        if right >= nums.Length then
            acc
        else
            let product' = product * nums.[right]
            let left', product'' = moveLeft nums left right product'
            let acc' = if product'' < k then acc + right - left' + 1 else acc
            numSubarrayProductLessThanK' nums left' (right + 1) product'' acc'

    numSubarrayProductLessThanK' (List.toArray nums) 0 0 1 0