Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
 
Example 1:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

 
Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # save all even subarray's length which between odds
        edge = []
        res = 0
        count = 0
        for i in nums:
            # odd
            if i % 2:
                # +1 because range from 0 to count when doing combination
                edge.append(count+1)
                count = 0
            # even
            else:
                count += 1
        edge.append(count+1)
        # no enough odd
        if len(edge)-1 < k:
            return 0
        else:
            # combination
            for i in range(len(edge)-k):
                res += edge[i] * edge[i+k]
            return res

class Solution:
    def numberOfSubarrays(self, A: List[int], k: int) -> int:
        d = []
        n = len(A)
        res = 0
        count = 1
        for i in range(n):
            if (A[i] % 2):
                d.append(count)
                count = 1
            else:
                count += 1
        d.append(count)
        for x,y in zip(d,d[k:]):
            res += x * y
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        l = [0]*(len(nums)+1)
        for i,n in enumerate(nums):
            l[i+1]=l[i]+n%2
        c = Counter(l)
        #print(l)
        return sum(c[x-k]*c[x] for x in c)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix = {0: 1}
        count = 0
        result_count = 0
        
        for num in nums:
            if num % 2:
                count += 1
                
            prefix[count] = prefix.get(count, 0) + 1
            
            result_count += prefix.get(count - k, 0)
        return result_count

from collections import defaultdict
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def helper(k):
            start=end=counter=res=0
            while end<len(nums):
                if nums[end]%2!=0:
                    counter+=1
                end+=1
                while counter>k:
                    if nums[start]%2!=0:
                        counter-=1
                    start+=1
                res+=(end-start)
            return res
        return helper(k)-helper(k-1)
                    


from collections import Counter

class Solution:
    def numberOfSubarrays(self, A, k):
        count = Counter([0])
        
        ans = 0
        psum = 0
        for v in A:
            psum += v % 2
            ans += count[psum - k]
            count[psum] += 1
        
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        for i in range(len(nums)): nums[i] = nums[i] % 2
        mp = defaultdict(int)
        mp[0] = 1
        csum, ans = 0, 0
        
        for i, num in enumerate(nums):
            csum += num
            ans += mp[csum - k]
            mp[csum] += 1
        
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = count = nice_count = odd_count = 0
        for j in range(len(nums)):
            if nums[j] % 2 == 1:
                odd_count += 1
                count = 0
            while odd_count == k:
                odd_count -= nums[i] % 2
                i += 1
                count += 1
            nice_count += count
        return nice_count


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        s = []
        evencnt = 0
        for num in nums:
            if num % 2 == 1:
                s.append(evencnt)
                evencnt = 0
            else:
                evencnt += 1
        s.append(evencnt)
        res = 0
        for i in range(len(s) - k):
            res += (s[i]+1) * (s[i+k]+1)
        return res

class Solution:
    def numberOfSubarrays(self, nums, k):
        return self.atMost(nums, k) - self.atMost(nums, k - 1)
    
    def atMost(self, nums, k):
        if k < 0:
            return 0
        n = len(nums)
        right = 0
        cnt = 0
        res = 0
        for left in range(n):
            while right <= n - 1 and (cnt < k or nums[right] % 2 == 0):
                cnt += (nums[right] % 2 == 1)
                right += 1
            res += right - left
            cnt -= (nums[left] % 2 == 1)
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        blocks = [1]
        for num in nums:
            if num % 2 == 1:
                blocks.append(1)
                continue
            blocks[-1] += 1
        return sum(left * right for left, right in zip(blocks, blocks[k:]))

def solve(A, k):
    count = [0, 0]
    front = iter(A)
    ans = 0
    size = 0
    
    for v in A:
        count[v % 2] += 1
        size += 1
        while count[1] > k:
            count[next(front) % 2] -= 1
            size -= 1
        ans += size
        
    return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return solve(nums, k) - solve(nums, k - 1)
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        data = []
        curr = 0
        L = 0
        count = 0
        for num in nums:
            if num % 2 == 0:
                curr += 1
            else:
                L += 1
                data.append(curr)
                curr = 0
        if L < k:
            return 0
        end = 0
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] % 2 == 1:
                break
            end += 1
        for i in range(k - 1, L - 1):
            count += (data[i - k + 1] + 1) * (data[i + 1] + 1)
        return count + (end + 1) * (data[-k] + 1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = count = nice_count = odd_count = 0
        for j in range(len(nums)):
            if nums[j] % 2 == 1:
                odd_count += 1
                count = 0
            while odd_count == k:
                odd_count -= nums[i] % 2
                i += 1
                count += 1
            nice_count += count
        return nice_count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(nums, k):
            i, j, count, res = 0, 0, 0, 0
            while j<len(nums):
                if nums[j]%2==1:
                    count+=1
                while count>k:
                    if nums[i]%2==1:
                        count-=1
                    i+=1
                res+=j-i+1
                j+=1
            return res
        
        return at_most(nums,k)-at_most(nums,k-1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        odds = [-1]
        for i in range(len(nums)):
            if nums[i]&1: odds.append(i) # &1 should be faster than %2
        odds.append(len(nums))
        i, count= 1, 0
        while i+k-1<len(odds)-1:
            count += (odds[i]-odds[i-1])*(odds[i+k]-odds[i+k-1])
            i += 1
        return count


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        occur = collections.defaultdict(int)
        
        occur[0] = 1
        runsum = 0
        count = 0
        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                nums[i] = 0
            else:
                nums[i] = 1
            runsum += nums[i]
            if (runsum - k) in occur:
                count += occur[runsum-k]
            
            occur[runsum] +=1
            
        return count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        s = 0
        e = 0
        l = len(nums)
        total = 0
        num_odd = 0
        ae = 0
        while s < l:
            
            
            
            while e < l and num_odd != k:
                if nums[e] % 2 != 0:
                    # odd
                    num_odd += 1

                e += 1
                    

            if num_odd == k:
                if ae < e:
                    ae = e
                    while ae < l and nums[ae] %2 == 0:
                        ae += 1
                total += (ae-(e-1))
                #print(s, e, \"total = \", total, \"added = \", l-(e-1), \"num_odd = \", num_odd)  
            
            if nums[s] % 2 != 0:
                num_odd -= 1
            s += 1
            
        return total
            
            
            
            
            
        


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        num_odds = defaultdict(int, {0:1})
        total = 0
        
        running = 0
        for n in nums:
            running += n % 2
            total += num_odds[running - k]
            
            num_odds[running] += 1
        
        return total

from collections import defaultdict

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        
        
        seen = defaultdict(int)
        seen[0] = 1
        
        output = 0
        odds = 0
        
        for i in range(0,len(nums)):
            
            if nums[i]%2 != 0:
                odds += 1
            
            # print(odds-k, seen)
            if odds - k in seen:
                # print(i, seen, odds -k )
                output += seen[odds-k]
            
            seen[odds] += 1
        
        return output
            


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        num_nice = 0
        i = 0
        count = 0
        for num in nums:
            if num & 1:
                k -= 1
                count = 0
            while k == 0:
                k += nums[i] & 1
                count += 1
                i += 1
            num_nice += count
        return num_nice

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        '''
        If we replace the odds with 1's and evens with 0's then the problem 
        is similar to finding number of subarrays with sum = k
        '''
        '''
        dp = collections.defaultdict(int)
        dp[0] = 1
        cur = 0
        result = 0
        for i in range(len(nums)):
            cur += nums[i]%2
            diff = cur-k
            if diff in dp:
                result += dp[diff]
            dp[cur]+=1
        
        return result
        '''
        def atMost(k):
            l, result = 0,0
            for i in range(len(nums)):
                k-=nums[i]%2
                while k < 0:
                    k+=nums[l]%2
                    l+=1
                result += i-l+1
            return result
        
        return atMost(k) - atMost(k-1)
                    
    
    
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        output = 0
        
        count_odd = 0
        l = 0
        for r, n in enumerate(nums):
            
            count_odd += int(n % 2 == 1)
            
            if count_odd == k:
                n_even = 1
                for j in range(r+1, len(nums)):
                    if nums[j] % 2 == 0:
                        n_even += 1
                    else:
                        break
            
            while count_odd == k:
                output += n_even
                count_odd -= int(nums[l] % 2 == 1)
                l += 1
        
        return output

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt=0
        d={}
        d[0]=1
        for i in nums:
            if i%2:
                cnt+=1
            if cnt in d:
                d[cnt]+=1
            else:
                d[cnt]=1
                
        ans=0
        for key in d:
            if k+key in d:
                ans+=(d[key]*d[k+key])
        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cur = res = i = 0
        for j in range(len(nums)):
            if nums[j] % 2 != 0:
                k -= 1
                if k == 0:
                    cur = 1
                    while nums[i] % 2 == 0:
                        cur += 1
                        i += 1
                    k += 1
                    i += 1
                    res += cur
            else:
                res += cur
        return res 


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        '''
        This is not an atmost/atleast constraint. 
        Soln pattern is different for atleast constraint
        refer this https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/
        This is an exact constraint, so different thinking is required
        
        Nice solution is explained here
        https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419378/JavaC%2B%2BPython-Sliding-Window-O(1)-Space
        Two methods are given.
        1) uses standard templete to find subarray with atmost k odd numbers
        2) modifies this template slightly to accomodate exactly k odd numbers constraint
        '''
        # return self.sol2(nums, k)
        return self.sol1(nums, k) - self.sol1(nums, k-1)
    
    def sol1(self, nums, k):
        '''
        Exactly k ones = atMost(k ones) - atMost(k-1 ones)
        '''
        start = 0
        odds = 0
        res = 0
        for end in range(len(nums)):
            odds += nums[end] & 1
            while odds > k:
                '''Inc start till constraint is violated'''
                odds -= nums[start] & 1
                start += 1
            
            '''
            This will add all sub arrays from size 1,2..end-start for every iteration
            Since we are doing atMost(k) even if sub array does not contain any odd number we still have to add it to res even if its size is 1
            '''
            res += end - start + 1
            # print(res)    
        return res
    
    def sol2(self, nums, k):
        start = 0
        odds = 0
        res = 0
        count = 0
        for end in range(len(nums)):
            if nums[end] & 1: # nums[end] is odd
                odds += 1
                count = 0 # reset counter to avoid repeated addition to result
                
            while odds >= k:
                if nums[start] & 1:
                    odds -= 1
                    
                start += 1
                count += 1
                # print(end, start)
                
                
            res += count
                
        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        odds = [-1]
        for i in range(len(nums)):
            if nums[i]&1: odds.append(i) # &1 should be faster than %2
        odds.append(len(nums))
        i, count= 1, 0
        while i+k-1<len(odds)-1:
            count += (odds[i]-odds[i-1])*(odds[i+k]-odds[i+k-1])
            i += 1
        return count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(k):
            count=i=res=0
            for j, v in enumerate(nums):
                if v%2: count+=1
                while count>k:
                    if nums[i]%2: count-=1
                    i+=1
                res+=j-i+1
            return res
        
        return atMost(k)-atMost(k-1)
        


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atmost(k):
            res=i=0
            for j in range(len(nums)):
                k-=nums[j]%2
                while k < 0:
                    k+=nums[i]%2
                    i+=1
                res += j-i+1
            return res
        return atmost(k)-atmost(k-1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # Sliding window approach
        num_odd_numbers = 0
        foo = 0
        left = 0
        right = 0
        
        # We keep an extra count variable here: after we break out of the inner while loop, 
        # we will have the number of nice subarrays recorded as count, then we will continue to expand the right 
        # part of the window, as long as it doesn't hit another odd number which will make the window 
        # unsatisfactory (this is where we reset the count to 0), there will be the same amount more of the 
        # satisfactory window (imagine when K = 2, if [1, 1, 2, 2] is satistfactory, [1, 1, 2, 2, 2] is statisfactory too).
        count = 0
        num_nice_arrays = 0
        
        while right < len(nums):
            r_n = nums[right]
            if r_n % 2 == 1:
                count = 0
                num_odd_numbers += 1
                
            while num_odd_numbers == k:
                # Try to subtract the window
                l_n = nums[left]
                if l_n % 2 == 1:
                    num_odd_numbers -= 1
                left += 1
                count += 1
              
            num_nice_arrays += count
            right += 1
            
        return num_nice_arrays

class Solution:
    def numberOfSubarrays(self, nums, k):
        return self.atMost(nums, k) - self.atMost(nums, k - 1)
    
    def atMost(self, nums, k):
        if k < 0:
            return 0
        n = len(nums)
        right = 0
        res = 0
        cnt = 0
        for left in range(n):
            while right <= n - 1 and (cnt < k or nums[right] % 2 == 0):
                cnt += (nums[right] % 2 == 1)
                right += 1
            res += right - left
            cnt -= (nums[left] % 2 == 1)
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(A, k):
            res = i = 0
            for j in range(len(A)):
                k -= A[j] % 2
                while k < 0:
                    k += A[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(nums, k) - atMost(nums, k - 1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        res = count = odd_count = i = 0
        for j in range(len(nums)) :
            if nums[j] % 2 == 1 :
                odd_count += 1
                count = 0                
            while odd_count == k:
                odd_count -= nums[i] % 2
                i += 1 
                count += 1
            res += count
        return res
            
            
                
                
                


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        
        ## NOT MY CODE TRIALS
        A=nums
        def atMost(k):
            res = i = 0
            for j in range(len(A)):
                k -= A[j] % 2
                while k < 0:
                    k += A[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(k) - atMost(k - 1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        def AtMostK(k):
            
            left = 0
            count = 0
            currK = 0
            
            for index in range(len(nums)):
                
                if nums[index] % 2 == 1:
                    currK += 1
                    
                while currK > k:
                    if nums[left] % 2 == 1:
                        currK -= 1
                    
                    left += 1
                
                count += index - left + 1
            
            return count
        
        return AtMostK(k) - AtMostK(k - 1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        noOfNiceSubArrays = 0
        even = 0
        oddList = []
        for i in range(n):
            if nums[i]%2==0:
                even += 1
            else:
                oddList.append(even)
                even = 0
        oddList.append(even)
        # print(oddList)
        for i in range(len(oddList)-k):
            noOfNiceSubArrays += (oddList[i]+1)*(oddList[i+k]+1)
            
        return noOfNiceSubArrays
                
    
    
#     [1,1,2,1,1]
#     [0, 0, ]


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        odds = [0]*len(nums)
        n = len(nums)
        d = {}
        if nums[0]%2 == 1:
            odds[0] = 1
        else:
            odds[0] = 0
            
        # d[odds[0]] = d.setdefault(0, []) + [1]
        odds = [0] + odds
        d[0] = d.setdefault(0, []) + [0]
        
        count = 0
        for i in range(1, n+1):
            if nums[i-1]%2 == 1:
                odds[i] = odds[i-1] + 1
            else:
                odds[i] = odds[i-1]
            
            if odds[i] - k in d:
                count += len(d[odds[i] - k])
            d[odds[i]] = d.setdefault(odds[i], []) + [i] 
        
        return (count)
                        


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def helper(k):
            ans = i = 0
            for j in range(len(nums)):
                k -= nums[j]%2
                while k < 0:
                    k += nums[i]%2
                    i += 1
                ans += j - i + 1
            return ans
        return helper(k) - helper(k-1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return self.numberOfAtmostK(nums, k) - self.numberOfAtmostK(nums, k-1)
    def numberOfAtmostK(self, nums, k):
        l, r, count, res = 0, 0, 0, 0
        while r < len(nums):
            if nums[r] % 2 == 1:
                count += 1
            while count > k:
                if nums[l] % 2 == 1:
                    count -= 1
                l += 1
            res += r - l + 1
            r += 1
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        def at_most(nums, k):
            cnts = l = res = 0
            for r in range(len(nums)):
                cnts += nums[r] % 2

                while cnts > k:
                    cnts -= nums[l] % 2
                    l += 1

                res += r - l + 1
            return res
                
        return at_most(nums, k) - at_most(nums, k-1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = count = res = 0
        for j in range(len(nums)):
            if nums[j] & 1:
                k -= 1
                count = 0
            while k == 0:
                k += nums[i] & 1
                i += 1
                count += 1
            res += count
        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix_sum = [0] *len(nums)
        start = {}

        prefix_sum[0]= 0 if nums[0]%2==0 else 1
        if prefix_sum[0] == 0:
            start[0] = 0
        else:
            start[1]=0
        
        for i in range(1,len(nums)):
            prefix_sum[i]=prefix_sum[i-1] if nums[i]%2==0 else prefix_sum[i-1]+1
            if prefix_sum[i-1]!=prefix_sum[i]:
                start[prefix_sum[i]] = i
        out = 0
        start[prefix_sum[0]] = 0
        start[prefix_sum[len(nums)-1]] = len(nums)-1


        for i in range(len(nums)):
            print(i)
            if prefix_sum[i] >= k and nums[i]%2!=0:
                if prefix_sum[i]-(k-1) in start:
                    beg = start[prefix_sum[i]-(k-1)]
                else:
                    beg = 0
                # count even numbers before beg
                j = beg - 1
                left_count = 0
                while j >=0:
                    if nums[j] %2==0:
                        left_count+=1
                    else:
                        break
                    j-=1
                # count even numbers after i
                j = i+1
                right_count = 0
                while j <len(nums):
                    if nums[j] %2==0:
                        right_count+=1
                    else:
                        break
                    j+=1
                out += ((left_count + 1)*(right_count+1))                        
        return out

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix_odd = defaultdict(int)
        prefix_odd[0] = 1
        ans = count = 0
        for num in nums:
            if num % 2:
                count += 1
            prefix_odd[count] += 1
        for p in prefix_odd:
            if p - k in prefix_odd:
                ans += prefix_odd[p] * prefix_odd[p - k]
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        last = 0
        hsh = {}
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                nums[i] = 1
            else:
                nums[i] = 0
                
            nums[i] += last
            last = nums[i]
            if nums[i] not in hsh:
                hsh[nums[i]] = []
            hsh[nums[i]].append(i)
        
        count = 0
        if k in hsh:
            count = len(hsh[k])
        
        for i in range(len(nums)):
            x = nums[i]
            if x + k in hsh:
                for v in hsh[x+k][::-1]:
                    if v < i:
                        break
                    count += 1
        return count
                
            
            
        
                
        


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        blocks = [0]
        for num in nums:
            if num % 2 == 1:
                blocks.append(0)
                continue
            blocks[-1] += 1
        ans = 0
        for left, right in zip(blocks, blocks[k:]):
            ans += (left + 1) * (right + 1)
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix, odd_cnt, ans = {0: 1}, 0, 0
        for num in nums:
            if num % 2 == 1: odd_cnt += 1
            prefix[odd_cnt] = prefix.get(odd_cnt, 0) + 1
            if odd_cnt - k in prefix: ans += prefix[odd_cnt - k]
        
        return ans
                
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = count = res = 0
        for j in range(len(nums)):
            if nums[j] & 1:
                k -= 1
                count = 0
            while k == 0:
                k += nums[i] & 1
                i += 1
                count += 1
            res += count
        return res


from collections import defaultdict
class Solution:
#     def numberOfSubarrays(self, nums: List[int], k: int) -> int:
#         hashmap = defaultdict(int)
#         hashmap[0] = 1
#         accSum, total = 0, 0
#         for n in nums:
#             accSum += 1 if n % 2 ==1 else 0
#             if accSum - k in hashmap:
#                 total += hashmap[accSum - k]
#             hashmap[accSum] += 1
            
#         return total
       def numberOfSubarrays(self, A, k):
            i = count = res = 0
            for j in range(len(A)):
                if A[j] & 1:
                    k -= 1
                    count = 0
                while k == 0:
                    k += A[i] & 1
                    i += 1
                    count += 1
                res += count
            return res
                
    


class Solution:
    def numberOfSubarrays(self, A: List[int], B: int) -> int:
        
        import collections
        q, k, temp, count = collections.deque(),0,0,0
    
        if B == 0:
            for i in range(len(A)):
                if A[i]%2 == 0:
                    temp = temp+1
                elif A[i]%2 !=0:
                    count = count + int((temp*(temp+1))/2)
                    temp = 0
            count = count + int((temp*(temp+1))/2)
            return count
        
        while len(q)<B and k<len(A):
            if A[k]%2 == 0: 
                temp = temp +1
            elif A[k]%2 == 1:
                q.append(temp)
                temp = 0
            k = k+1
        
        if len(q)<B:
            return 0

        temp = 0
        for i in range(k,len(A)):
            if A[i]%2 == 0:
                temp = temp + 1
            elif A[i]%2 != 0:
                count = count + (q[0]+1)*(temp+1)
                q.append(temp)
                q.popleft()
                temp = 0
                
        count = count + (q[0]+1)*(temp+1)
        return count


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix = collections.defaultdict(int)
        prefix[0] = 1
        pre = ans = 0
        for n in nums:
            pre += n & 1
            prefix[pre] += 1
            ans += prefix[pre-k]
        
        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        idxes = []
        
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                idxes.append(i)
                
        if len(idxes) < k:
            return 0
        res = 0
        for i in range(k-1, len(idxes)):
            l = -1 if i-k+1 == 0 else idxes[i-k]
            r = len(nums) if i == len(idxes)-1 else idxes[i+1]
            
            res += (idxes[i-k+1] - l) * (r - idxes[i])

        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # for k = 0, there is one subarray
        dic = {0: 1}
        count = 0 
        nice = 0
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                count += 1
            
            if count-k in dic:
                nice += dic[count-k] 
            
            dic[count] = dic.get(count, 0) + 1
        
        return nice

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        res = 0
        i = j = 0
        while i <= j:
            while k > 0 and j < len(nums):
                if nums[j] % 2 == 1:
                    k -= 1
                j += 1
            
            if k != 0:
                return res
            
            res += 1
            
            t = j
            while t < len(nums):
                if nums[t] % 2 == 0:
                    res += 1
                    t += 1
                else:
                    break
            
            if nums[i] % 2 == 1:
                k += 1
            i += 1
        
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        deque = collections.deque()
        deque.append(1)
        ans = 0
        for num in nums:
            if num % 2 == 0:
                deque[-1] += 1
                continue
            if len(deque) == k + 1:
                ans += deque[0] * deque[-1]
                deque.popleft()
            deque.append(1)
        if len(deque) == k + 1:
            ans += deque[0] * deque[-1]
        return ans

from collections import Counter

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        count = Counter([0])
        
        ans = 0
        psum = 0
        for v in map(lambda x: x % 2, nums):
            psum += v
            ans += count[psum - k]
            count[psum] += 1
        
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        count = 0
        res = 0
        odd = 0
        j = 0
        for i in range(len(nums)):
            if nums[i] & 1:
                odd += 1
                if odd >= k:
                    count = 1
                    if odd > k:
                        j += 1
                        odd -= 1
                    while nums[j] & 1 == 0:
                        j += 1
                        count += 1
                res += count
            else:
                res += count
        return res


def solve(A, k):
    count = [0, 0]
    lower = (x % 2 for x in A)
    
    ans = 0
    for x in (x % 2 for x in A):
        count[x] += 1
        while count[1] > k:
            count[next(lower)] -= 1
        ans += sum(count)

    return ans
    

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return solve(nums, k) - solve(nums, k - 1)
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        left = collections.defaultdict(int)
        odd = 0
        res = 0
        for n in nums:
            left[odd] += 1
            odd += n&1
            if odd - k in left:
                res += left[odd-k]
        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        nums = [n % 2 for n in nums]
        
        def atMost(k):
            ans, j = 0, 0
            for i, n in enumerate(nums):
                k -= n
                while k < 0:
                    k += nums[j]
                    j += 1
                ans += i - j + 1
            return ans
        
        return atMost(k) - atMost(k - 1)
        
        
        
#         ans, i, j, cnt = 0, 0, 0, 0
#         for i, n in enumerate(nums):
#             cnt += nums[i]
#             if cnt == k:
#                 if nums[i]:
#                     cur = nums[j:].index(1)
#                 ans += cur + 1
#             elif cnt > k:
#                 j += cur + 1
#                 cnt -= 1
#                 cur = nums[j:].index(1)
#                 ans += cur + 1
#         return ans
        
        
#         def atMost(k):
#             res = i = 0
#             for j in xrange(len(A)):
#                 k -= A[j] % 2
#                 while k < 0:
#                     k += A[i] % 2
#                     i += 1
#                 res += j - i + 1
#             return res

#         return atMost(k) - atMost(k - 1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        odd_count = tmp_count = j = 0    
        final_count = 0

        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                odd_count += 1
                tmp_count = 0

            while odd_count == k:
                odd_count -= nums[j] % 2
                j += 1
                tmp_count += 1

            final_count += tmp_count

        return final_count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cache = {0: [-1]}
        cnt = 0
        odds = 0
        for i, num in enumerate(nums):
            if num % 2:
                odds += 1
            if odds - k in cache:
                cnt += len(cache[odds-k])
            x = cache.setdefault(odds, [])
            x.append(odds)
        return cnt

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
         
        d = collections.defaultdict(int)
        d[0] = 1
        cur_sum = 0
        ans = 0
        for i,v in enumerate(nums):
            cur_sum += v%2
            if cur_sum -k in d:
                ans += d[cur_sum -k]
            d[cur_sum] += 1
        
        return ans
                
            
        
         
                


from collections import deque

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # nums = nums[:]  # if we need to avoid tampering with nums
        nums.append(1)  # Dummy odd value to avoid final value edge case
        
        odds = deque()
        odds.append(-1)
        
        total = 0
        for i, val in enumerate(nums):
            if val % 2:
                odds.append(i)
                if len(odds) > k + 2:
                    odds.popleft()
                if len(odds) == k + 2:
                    total += (odds[1] - odds[0]) * (odds[-1] - odds[-2])
                
        return total

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
      odd_pos = [pos for pos, e in enumerate(nums) if e % 2 == 1]

      if len(odd_pos) < k:
        return 0
      
      spaces = []
      prev_pos = -1
      for pos in odd_pos:
        spaces.append(pos - prev_pos)
        prev_pos = pos
      spaces.append(len(nums) - prev_pos)
      
      res = 0
      for i in range(len(spaces) - k):
        res += spaces[i] * spaces[i + k]
        
        
      return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        output = 0
        
        count_odd = 0
        l = 0
        for r, n in enumerate(nums):
            
            count_odd += int(n % 2 == 1)
            
            n_even = 1
            for j in range(r+1, len(nums)):
                if nums[j] % 2 == 0:
                    n_even += 1
                else:
                    break
            
            while count_odd == k:
                output += n_even
                count_odd -= int(nums[l] % 2 == 1)
                l += 1
        
        return output

def solve(A, k):
    count = [0, 0]
    lower = iter(A)
    
    ans = 0
    for x in A:
        count[x % 2] += 1
        while count[1] > k:
            count[next(lower) % 2] -= 1
        ans += sum(count)

    return ans
    

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return solve(nums, k) - solve(nums, k - 1)
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        temp_arr = []
        temp_count = 0
        for n in nums:
            if n % 2 != 0:
                temp_arr.append(temp_count)
                temp_count = 0
            else:
                temp_count = temp_count +1
        
        temp_arr.append(temp_count)
        if len(temp_arr) -1 < k:
            return 0
        #print(temp_arr)
        i = k -1
        count = 0
        while i < len(temp_arr) -1:
            start_len = temp_arr[i-k+1] +1
            end_len = temp_arr[i+1] +1
            #print(start_len * end_len)
            count = count + (start_len * end_len)
            i = i+1
        return count
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(k):
            res = i = 0
            for j in range(len(nums)):
                k -= nums[j] % 2
                while k < 0:
                    k += nums[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(k) - atMost(k - 1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = count = res = 0
        for j in range(len(nums)):
            if nums[j] & 1:
                k -= 1
                count = 0
            while k == 0:
                k += nums[i] & 1
                i += 1
                count += 1
            res += count
        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        front,end=0,0
        tot=0
        output=0
        ct=0
        while end < len(nums):
            if 1 & nums[end]:
                tot+=1
                ct=0
            end+=1
            while tot==k:
                tot-=nums[front]&1
                front+=1
                ct+=1
            output+=ct
        return output

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt = 0
        accNum = {}
        ans = 0
        accNum[0] = 1
        for x in nums:
            if x%2:
                cnt += 1
            if cnt not in accNum:
                accNum[cnt] = 1
            else:
                accNum[cnt] += 1
            if cnt-k in accNum:
                ans += accNum[cnt - k]
        return ans

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

        aDict = collections.defaultdict(int)
        aDict[0] = 1

        aSum = 0
        result = 0

        for i in nums:
            if i % 2 == 1:
                aSum += 1
            if aSum - k in aDict:
                result += aDict[aSum - k]
            aDict[aSum] += 1
        return result

class Solution:
    def numberOfSubarrays(self, A: List[int], k: int) -> int:
        d = []
        res = 0
        count = 1
        for a in A:
            if (a % 2):
                d.append(count)
                count = 1
            else:
                count += 1
        d.append(count)
        for x,y in zip(d,d[k:]):
            res += x * y
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # Corner cases
        if k > n:
            return 0
        
        # We will use 4 pointers: p1, p2, p3, p4
        # p1 will initially start at -1. It will always point to the \"previous\" odd number
        # that we DONT want to include the in the current count
        # p2 will point to the first odd number that we want to count
        # p3 will point the the kth odd number starting from p2's odd number
        # p4 will point to the next odd number after p3 if it exists, else will point to n
        # Given p1, p2, p3, p4, the number of nice subarrays in this window equals (p2-p1)*(p4-p3)
        # After that, we set p1 to p2, p3 to p4. Then move p4 (if you can) to the next odd number, and move
        # p2 to the next odd number. Do this until you can't move p4 anymore.
        ans = 0
        p1 = p2 = p3 = p4 = -1
        while p4 < n:
            # Move p2 to the next odd number
            p2 += 1
            while p2 < n and nums[p2] % 2 == 0:
                p2 += 1
                if p2 == n:
                    return ans
            # p2 now points to the 1st odd number
            # Now move p3 to the kth odd number (Note that for k=1 p3 coincides with p2)
            # For the first time the loop is executed, we find the k-th 1 by moving forward one index at a time.
            # For the second loop onward, we simply set p3 to p4. Also note that because we entered the loop,
            # p4 < n, hence p4 must point to a 1, hence we can simply set p3 to p4.
            if p4 == -1:
                p3 = p2
                remaining = k-1
                while p3 < n and remaining:
                    p3 += 1
                    if p3 == n:
                        return ans
                    if nums[p3] % 2 == 1:
                        remaining -= 1
            else:
                p3 = p4
            # p3 now points to the kth odd number
            # Now move p4 to the next odd number
            p4 = p3 + 1 # p3 is at most n-1, because we would have returned otherwise.
            while p4 < n:
                if nums[p4] % 2 == 1:
                    break
                p4 += 1
            # p4 is now either n or the next odd number after p3
            # Now compute the number of nice subarrays in this window and add to ans
            ans += (p2-p1)*(p4-p3)
            # To set up for the next round, set p1 to p2
            p1 = p2
        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        memo = {0: 1}
        count = 0
        res = 0
        for n in nums:
            if n % 2 == 1:
                count += 1
            if count - k in memo:
                res += memo[count - k]
            memo[count] = memo.get(count, 0) + 1
        return res

class Solution:
    
    def checkOdd(self, num):
        if num % 2 == 0:
            return False
        return True

    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddIndices = []
        for i in range(len(nums)):
            if self.checkOdd(nums[i]):
                oddIndices.append(i)
        start = 0
        end = k - 1
        i = 0
        count = 0
        while end < len(oddIndices):
            if end == len(oddIndices) - 1:
                j = len(nums) - 1
            else:
                j = oddIndices[end + 1] - 1
            
            count = count + (oddIndices[start] -i + 1) * (j - oddIndices[end] + 1)
            i = oddIndices[start] + 1
            start = start + 1
            end = end + 1
        return count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        prefix_sum = 0
        
        dict_odds = {0 : 1}
        
        rs = 0
        
        for i, num in enumerate(nums):
            if num % 2 == 1: # odd
                prefix_sum += 1
            
            if prefix_sum not in dict_odds:
                dict_odds[prefix_sum] = 1
            else:
                dict_odds[prefix_sum] = dict_odds[prefix_sum] + 1            
            
            if (prefix_sum - k) in dict_odds:
                rs += dict_odds[(prefix_sum - k)]
            
                
        
        
        return rs


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        index_list = []
        index_list.append(-1)
        for i in range(0, len(nums)):
            if nums[i] % 2 == 1:
                index_list.append(i)
        index_list.append(len(nums))
        if len(index_list) == 0:
            return 0
        left = 1
        right = 1
        k_count = 1
        count = 0
        while right < (len(index_list) - 1):
            if k_count == k:
                count += (index_list[left] - index_list[left - 1]) * (index_list[right + 1] - index_list[right])
                left += 1
                k_count -= 1
            else:
                k_count += 1
                right += 1
        return count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        memo = collections.defaultdict(int)
        memo[0] = 1
        count = 0
        res = 0
        for n in nums:
            if n % 2 == 1:
                count += 1
            if count - k in memo:
                res += memo[count - k]
            memo[count] += 1
        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        num_odd = 0
        start = 0
        output = 0
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                num_odd += 1
            while num_odd > k:
                if nums[start] % 2 == 1:
                    num_odd -= 1
                start += 1
            if num_odd == k:
                output += 1
                cur_start = start
                while nums[cur_start] % 2 == 0:
                    cur_start += 1
                    output += 1
        return output

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        adict = {0: 1}
        x = 0
        result = 0
        for i in nums:
            if i & 1 != 0:
                x += 1
            if x - k in adict:
                result += adict[x-k]
            adict[x] = adict.get(x, 0) + 1
        return result
            
            


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        rr = l = r = res = cnt = 0
        ll = -1
        n = len(nums)
        while r < n:
            x = nums[r]
            if x%2:
                if ll < l: ll = r
                cnt += 1
            if cnt == k:
                rr = r
                while r < n - 1 and nums[r + 1]%2 == 0: r += 1
                res += (ll - l + 1) * (r - rr + 1)
                l = ll + 1
                cnt -= 1
                ll += 1
                while ll < n and nums[ll]%2 == 0: ll += 1
            r += 1
        return res
            
                
                


from collections import defaultdict
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        if len(nums) < k:
            return 0
        
        # Cummulative count of number of odds
        num_odd = 0
        # Store number of sub-arrays with count [key] previously seen
        seen = defaultdict(int)
        seen[0] = 1  # Empty subarray has 0 odd numbers
        
        ret = 0
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                num_odd += 1
            key = num_odd - k
            ret += seen[key]
            seen[num_odd] += 1
        return ret

class Solution:
    def numberOfSubarrays(self, A: List[int], k: int) -> int:
        d = []
        res = 0
        count = 1
        for a in A:
            if (a % 2):
                d.append(count)
                count = 1
            else:
                count += 1
        d.append(count)
        m = len(d)
        for i in range(m - k):
            res += d[i] * d[i+k]
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddIndices = []
        for i in range(len(nums)):
            if self.checkOdd(nums[i]):
                oddIndices.append(i)
        start = 0
        end = k - 1
        i = 0
        count = 0
        while end < len(oddIndices):
            if end == len(oddIndices) - 1:
                j = len(nums) - 1
            else:
                j = oddIndices[end + 1] - 1
            count = count + (oddIndices[start] - i + 1) * (j - oddIndices[end] + 1)
            i = oddIndices[start] + 1
            start = start + 1
            end = end + 1
        return count
            
            
    def checkOdd(self, num):
        if num % 2 == 0:
            return False
        return True

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        count = 0
        dic = defaultdict(int)
#        cum sum
        dic[0] = 1
        ans = 0 
        
        for i in range(1,len(nums)+1):
            count += nums[i-1]%2     
            if (count-k) in list(dic.keys()):
                ans += dic[count-k]
            dic[count] += 1   
        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        odd_indeces = []
        for i, elem in enumerate(nums):
            if elem % 2 != 0:
                # is odd
                odd_indeces.append(i)
        
        if len(odd_indeces) < k:
            return 0
        
        output = 0 
        
        print(odd_indeces)
        
        i = 0 
        while i + k <= len(odd_indeces): 
            first, last = odd_indeces[i], odd_indeces[i + k - 1]
            if first == 0:
                leftdist = 1
            elif i == 0:
                leftdist = first + 1
            else: 
                leftdist = odd_indeces[i] - odd_indeces[i - 1]
                
            if last == len(nums) - 1:
                rightdist = 1
            elif i + k - 1 == len(odd_indeces) - 1:
                rightdist = len(nums) - odd_indeces[i + k - 1]
            else:
                rightdist = odd_indeces[i + k] - odd_indeces[i + k - 1]
                
            output += leftdist * rightdist
                
            i += 1
        return output
                
                


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i, count, ans = 0, 0, 0
        for num in nums:
            if num % 2 == 1: # odd number
                k -= 1
                count = 0
            while k == 0:
                k += nums[i] % 2
                i += 1
                count += 1
            ans += count

        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = i = count = 0
        for j in range(len(nums)):
            if nums[j] & 1:
                k -= 1 
                count = 0
            while k == 0:
                k += nums[i] & 1
                i += 1
                count += 1
            ans += count
        return ans

def isOdd(num):
    return num % 2 == 1

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        items = [-1]
        for i, num in enumerate(nums):
            if isOdd(num):
                items.append(i)
        cnt = 0
        items.append(len(nums))
        for i in range(1, len(items) - 1):
            if i + k - 1 < len(items) - 1:
                left = items[i] - items[i-1]
                right = items[i+k] - items[i + k - 1]
                cnt += left * right
                    
        return cnt

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        flattened = [1 if num % 2 == 1 else 0 for num in nums]
        
        d = { 0: 1 }
        sum = 0
        total = 0
        
        for i in range(len(flattened)):
            sum += flattened[i]
            total += d.get(sum - k, 0)
            d[sum] = d.get(sum, 0) + 1
        
        return(total)


from collections import Counter

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddCounts = []
        oddCount = 0
        for num in nums:
            if num % 2 == 1:
                oddCount += 1
            oddCounts.append(oddCount)
        oddCountsIdxs = Counter(oddCounts)
        nice = 0
        for num in oddCounts:
            nice += oddCountsIdxs[num-k]
        nice += oddCountsIdxs[k]
        return nice

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        #双指针:循环右指针，嵌套左指针移动标准，夹杂计数。
        nums = [i%2 for i in nums]
        ans = 0
        tmp = 0
        n = len(nums)
        l = 0#左指针
        for r in range(n):
            #循环右指针
            if nums[r]==1:
                k -= 1
                tmp = 0
                
            while k == 0:
                #挪动左指针
                #print(l,r)
                k += nums[l]#踢出一个奇数即停止，重新回到右指针的循环
                l += 1
                tmp += 1
                
            
            ans += tmp
            #print(l,r,ans)
        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ln = len(nums)
        ret = 0
        
        for i in range(ln):
            if nums[i] % 2: nums[i] = 1
            else: nums[i] = 0

        #print(nums)
                
        mp = { 0 : 1 }
        cnt = 0

        for n in nums:
            cnt += n
            
            if cnt not in mp:
                mp[cnt] = 0
            mp[cnt] += 1
            
            if cnt - k in mp:
                ret += mp[cnt - k]
            

        return ret
        pass


# 20201007 ref
class Solution:
    def numberOfSubarrays(self, A: List[int], k: int) -> int:
        d = []
        n = len(A)
        res = 0
        count = 1
        for i in range(n):
            if (A[i] % 2):
                d.append(count)
                count = 1
            else:
                count += 1
        d.append(count)
        for x,y in zip(d,d[k:]):
            res += x * y
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0
        # d stores elements seen till now against every cumsum 
        d = {0:0}
        start = {}
        cumsum = 0
        for i, num in enumerate(nums):
            cumsum += num%2
            d[cumsum] = i+1
            if (cumsum not in start):
                start[cumsum] = i
            if cumsum==k:
                elems = d[0]
                ans += elems+1
            elif cumsum>k:
                elems = d[cumsum-k] - start.get(cumsum-k, -1)
                ans += elems
        return ans

from collections import deque

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        d,res = deque(),0
        d.append(-1)
        for i in range(0,len(nums)):
            if nums[i] % 2 == 1:
                d.append(i)
            if len(d) > k+1:
                d.popleft()
            if len(d) == k+1:
                a = d.popleft()
                b = d.popleft()
                res += b-a
                d.appendleft(b)
                d.appendleft(a)
        return res
                


from collections import Counter

class Solution:
    
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        lookup = Counter()
        lookup[0] = 1
        answer = accumulated_odd = 0

        for num in nums:
            if num % 2 == 1:
                accumulated_odd += 1
            answer += lookup[accumulated_odd - k]
            lookup[accumulated_odd] += 1
        return answer

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddnum = 0
        l, n = 0, len(nums)
        add = 1
        sums = 0
        for r in range(n):
            if nums[r] % 2 == 1:
                k -= 1
            while l < r and (k < 0 or nums[l] % 2 == 0):
                if k < 0:
                    add = 1
                else:
                    add += 1
                if nums[l] % 2 == 1:
                    k += 1
                l += 1
            if k == 0:
                sums += add
        return sums
            


from collections import Counter

class Solution:
    
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        lookup = Counter()
        # initializing
        lookup[0] = 1
        answer = accumulated_sum = 0
        
        for i in range(len(nums)):
            
            if nums[i] % 2 == 1:
                accumulated_sum += 1
            
            answer += lookup[accumulated_sum - k]
            lookup[accumulated_sum] += 1
            
        return answer
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddIdx = []
        
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                oddIdx.append(i)
            
        if len(oddIdx) < k:
            return 0
        
        print(oddIdx)
        arr = [oddIdx[0] + 1]
        for i in range(1, len(oddIdx)):
            temp = oddIdx[i] - oddIdx[i - 1]
            arr.append(temp)
        arr.append(len(nums) - oddIdx[-1])
            
        print(arr)
        res = 0
        for i in range(len(arr) - k):
            res += arr[i] * arr[i + k]
        
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        
        return self.atMostK(nums, k) - self.atMostK(nums, k - 1)
    
    def atMostK(self, nums, k):
        count = 0
        left = 0
        
        for right, right_num in enumerate(nums):
            k -= right_num % 2
            
            while k < 0:
                k += nums[left] % 2
                left += 1
            
            count += right - left + 1
        return count

# O(n) time and space 
# Keep a table of { odd number cnt: substrings with this odd number count}
# For example: {1: 2} means there are two substrings so far with one odd number
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        memo = collections.Counter()
        memo[0] = 1
        res = odds = 0
        
        for x in nums:
            if x % 2:
                odds += 1
            memo[odds] += 1
            res += memo[odds-k]
    
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        '''
        two passes, extact k times = at most k times - at most k - 1 times
        '''
        def atMost(A: List[int], k: int) -> int:
            i = ret = 0
            for j in range(len(A)):
                if A[j] & 1:
                    k -= 1
                while k < 0:
                    k += A[i] & 1
                    i += 1
                ret += j - i + 1
            return ret 
        
        return atMost(nums, k) - atMost(nums, k-1)
            


class Solution:
    def numberOfSubarrays(self, A: List[int], k: int) -> int:
        
        def atMost(k):
            res, lo = 0, 0
            for hi in range(len(A)):
                k -= A[hi] % 2
                while k < 0:
                    k += A[lo] % 2
                    lo += 1
                res += hi - lo + 1
            return res
        
        return atMost(k) - atMost(k-1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        return self.newConcept(nums,k) - self.newConcept(nums,k-1)
    
    
    
    
    
    def newConcept(self,nums,k):
        
        ans =0
        left = 0
        c = 0
        for i in range(len(nums)):
            if(nums[i]%2!=0):
                c+=1
            
           
                
            while(c>k):
                    
                    
                if(nums[left] % 2 != 0):
                    
                    c-=1
                        
                left+=1
                   
            ans+=i-left+1
        
        
        return ans


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        def atMost(m):
            if m < 0:
                return 0
            left = res = 0
            for right, x in enumerate(nums):
                m -= x & 1
                while m < 0:
                    m += nums[left] & 1
                    left += 1
                res += right - left + 1
            return res
        return atMost(k) - atMost(k - 1)
        
        # left = cnt = res = 0
        # for right, x in enumerate(nums):
        #     if x & 1:
        #         k -= 1
        #         cnt = 0
        #     while k == 0:
        #         k += nums[left] & 1
        #         left += 1
        #         cnt += 1
        #     # print(right, cnt)
        #     res += cnt
        # return res
        # def atMost(m):
        #     res = 0
        #     left = 0
        #     for right, x in enumerate(nums):
        #         m -= x & 1
        #         while m < 0:
        #             m += nums[left] & 1
        #             left += 1
        #         res += right - left + 1
        #     return res
        # return atMost(k) - atMost(k-1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        arr = list(map(lambda x: x%2, nums))
        n = len(arr)
        arr = [0] + list(itertools.accumulate(arr))
        hm = Counter()
        res = 0
        for i in arr:
            res += hm[i]
            hm[i+k] += 1
            
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
         
        l=len(nums)
        def atmost(k):
            res=0
            cnt=0
            j=0
            for i in range(l):
                if nums[i]%2==1:
                    cnt+=1
                while cnt>k:
                    if nums[j]%2==1:
                        cnt-=1
                    j+=1
                res+=i-j+1
            return res
        return atmost(k)-atmost(k-1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(k):
            left = 0
            count = 0
            res = 0
            for right in range(len(nums)):
                if nums[right] & 1:
                    count += 1
                while count > k and left <= right:
                    if nums[left] & 1:
                        count -= 1
                    left += 1
                
                res += right - left + 1
            
            return res
        
        return at_most(k) - at_most(k - 1)


class Solution:
    def numberOfSubarrays(self, A, k):
        @lru_cache(None)
        def atMost(k):
            res = i = 0
            for j in range(len(A)):
                k -= A[j] % 2
                while k < 0:
                    k += A[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(k) - atMost(k - 1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        positions = [-1]
        for i in range(len(nums)):
            if nums[i]%2==1: positions.append(i)
        positions.append(len(nums))
        total = 0
        for i in range(1, len(positions)-k):
            num_before = positions[i] - positions[i-1]
            num_after = positions[i+k] - positions[i+k-1]
            total += num_before * num_after
        return total


class Solution:
    def addOrIncrement(self, key, dictionary):
        if key in dictionary:
            dictionary[key] += 1
        else:
            dictionary[key] = 1
    
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if n < k:
            return 0
        
        ans = 0
        seen = {0: 1}
        curVal = 0
        for num in nums:
            curVal += 0 if num % 2 == 0 else 1
            if curVal - k in seen:
                ans += seen[curVal - k]
            self.addOrIncrement(curVal, seen)
        
        return ans


def isOdd(num):
    return num % 2 == 1

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        items = [-1]
        for i, num in enumerate(nums):
            if isOdd(num):
                items.append(i)
        cnt = 0
        items.append(len(nums))
        print(items)
        
        for i in range(1, len(items) - k):
            left = items[i] - items[i-1]
            right = items[i+k] - items[i + k - 1]
            cnt += left * right
                    
        return cnt

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        left_left = 0
        left_right = 0
        odds_left = 0
        odds_right = 0
        
        odds = 0
        
        ret = 0
        
        for right in range(n):
            odds_left += nums[right] % 2
            odds_right += nums[right] % 2
            
            while left_left <= right and odds_left > k:
                odds_left -= nums[left_left] % 2
                left_left += 1
            
            while left_right <= right and odds_right - nums[left_right] % 2 >= k:
                odds_right -= nums[left_right] % 2
                left_right += 1
            
            if odds_left == odds_right == k:
                ret += (left_right - left_left + 1)
                
        
        
        return ret

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return self.at_most(nums, k) - self.at_most(nums, k-1)
        
    def at_most(self, nums, k):
        i = 0
        res = 0
        for j, val in enumerate(nums):
            if val &1 == 1:
                k -= 1
            while k < 0:
                if nums[i] &1 == 1:
                    k += 1
                i += 1
            res += j - i + 1
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cache=collections.Counter({0:1})
        res,cnt_odd=0,0
        for i in range(len(nums)):
            if nums[i]%2==1:
                cnt_odd+=1
            res+=cache.get(cnt_odd-k,0)
            cache[cnt_odd]+=1
        return res


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(k):
            left = 0
            count = 0
            res = 0
            for right in range(len(nums)):
                count += nums[right] & 1
                while count > k and left <= right:
                    count -= nums[left] & 1
                    left += 1
                
                res += right - left + 1
            
            return res
        
        return at_most(k) - at_most(k - 1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        count = 0
        
        left = 0
        right = 0
        
        odd = 0
        
        while right < len(nums):
            
            if nums[right] % 2 == 1:
                odd += 1
            
            while left < right and odd > k:
                if nums[left] % 2 == 1:
                    odd -= 1
                left += 1
                    
            if odd == k:
                count += 1
                
            i = left
            while i < right and odd==k and nums[i] %2 == 0:
                count += 1
                i += 1
                
            right += 1
            
        return count

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        ans = 0
        cnt = 0
        lo = 0
        hi = 0
        cnt += nums[0]%2
        while lo<=hi and hi<len(nums):
            if cnt<k:
                hi += 1
                if hi<len(nums) and nums[hi]%2:
                    cnt += 1
            elif cnt>k:
                if lo<hi and nums[lo]%2:
                    cnt -= 1
                lo += 1
            else:
                ans += 1
                tempHi = hi
                while tempHi+1<len(nums) and nums[tempHi+1]%2 == 0:
                    ans += 1
                    tempHi += 1
                if lo<len(nums) and nums[lo]%2:
                    cnt -= 1
                lo += 1
                if hi<lo:
                    hi = lo
                    if hi<len(nums) and nums[hi]%2:
                        cnt += 1
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = count = ret = 0
        for j in range(len(nums)):
            if nums[j] & 1:
                k -= 1
                count = 0
            while k == 0:
                k += nums[i] & 1
                i += 1
                count += 1
            ret += count 
        return ret
            


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(k):
            ans = 0
            i = 0
            for j in range(len(nums)):
                k -= nums[j] % 2
                while k < 0:
                    k += nums[i] % 2
                    i += 1
                ans += j - i + 1
            return ans
        return at_most(k) - at_most(k - 1)

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

        def helper(k):
            i, j, count, res, = 0, 0, 0, 0
            while j < len(nums):
                if nums[j] % 2 == 1:
                    count += 1
                j += 1
                while count > k:
                    if nums[i] % 2 == 1:
                        count -= 1
                    i += 1
                res += j - i
            return res
        
        return helper(k) - helper(k - 1)



class Solution:
    def numberOfSubarrays(self, A, k):
        def atMost(k):
            res = i = 0
            for j in range(len(A)):
                k -= A[j] % 2
                while k < 0:
                    k += A[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(k) - atMost(k - 1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMost(K):
            b,e = 0,0
            ret = 0
            while e<len(nums):
                K-=nums[e]%2
                while K<0:
                    K+=nums[b]%2
                    b+=1
                ret+=e-b+1
                e+=1
            return ret
        return atMost(k) - atMost(k-1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        '''
        If we replace the odds with 1's and evens with 0's then the problem 
        is similar to finding number of subarrays with sum = k
        Space+Time: O(N)
        '''
        '''
        dp = collections.defaultdict(int)
        dp[0] = 1
        cur = 0
        result = 0
        for i in range(len(nums)):
            cur += nums[i]%2
            diff = cur-k
            if diff in dp:
                result += dp[diff]
            dp[cur]+=1
        
        return result
        '''
        '''
        # of subarrays sum equals k = # of subarrays sum <= k -
                                      # of subarrays sum <= (k-1)
        '''
        
        def atMost(k):
            l, result = 0,0
            for i in range(len(nums)):
                k-=nums[i]%2
                while k < 0:
                    k+=nums[l]%2
                    l+=1
                result += i-l+1
            return result
        
        #return atMost(k) - atMost(k-1)
    
        def atmost(k):
            res = 0
            l = 0
            for i in range(len(nums)):
                k -= nums[i]%2
                while k < 0:
                    k+=nums[l]%2
                    l+=1
                res+= i-l+1
            return res
        
        return atmost(k) - atmost(k-1)
                    
                
        
                    
    
    
    


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        if len(nums)==0:
            return 0
        preprocess = [0] * (len(nums) + 1) # preprocess[k] = num odd numbers in nums[:k]
        count = 0
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                count+=1
            preprocess[i+1] = count
        print(preprocess)
        cont_preprocess = [preprocess[0]]
        counts_cont = [1]
        last_el = preprocess[0]
        for i in range(1, len(preprocess)):
            if preprocess[i] == last_el:
                counts_cont[-1] += 1
            else:
                last_el = preprocess[i]
                cont_preprocess.append(last_el)
                counts_cont.append(1)
        result=0
        # number of (i<j) where a[j]-a[i] == k
        left_cursor = 0
        right_cursor = 0
        while left_cursor < len(cont_preprocess):
            diff = cont_preprocess[right_cursor] - cont_preprocess[left_cursor]
            if diff < k:
                right_cursor += 1
            elif diff == k:
                result += (counts_cont[right_cursor] * counts_cont[left_cursor])
                right_cursor += 1
            else:
                left_cursor += 1
            if right_cursor == len(cont_preprocess):
                right_cursor = len(cont_preprocess) - 1
                left_cursor += 1
        return result

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:        
        def at_most(k):
            start_ptr = 0
            result = 0
            
            for end_ptr in range(len(nums)):
                k -= nums[end_ptr] % 2
                
                while k < 0: # Already satisfied the condition, let's reduce the window size
                    k += nums[start_ptr] % 2
                    start_ptr += 1
                
                result += end_ptr - start_ptr + 1   # Now k just hit > 0, so we can compute this. No of subarray possible is end_ptr - start_ptr + 1. Start_ptr would have gotten as close as possible after this. 
            
            return result
            
        return at_most(k) - at_most(k - 1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        l, r, oddsCounter, res = 0, 0, 0, 0
        while r < len(nums):
            if nums[r] % 2 == 1:
                oddsCounter += 1
            while oddsCounter >k:
                if nums[l] % 2 == 1:
                    oddsCounter -= 1
                l += 1
            if oddsCounter == k: 
                res += 1 
            i = l
            while oddsCounter == k and i<r and nums[i]%2 == 0:
                res += 1
                i += 1
            r += 1   

        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        oddIdx = []
        
        for i in range(len(nums)):
            if nums[i] % 2 == 1:
                oddIdx.append(i)
            
        if len(oddIdx) < k:
            return 0
        
        arr = [oddIdx[0] + 1]
        for i in range(1, len(oddIdx)):
            temp = oddIdx[i] - oddIdx[i - 1]
            arr.append(temp)
        arr.append(len(nums) - oddIdx[-1])
            
        res = 0
        for i in range(len(arr) - k):
            res += arr[i] * arr[i + k]
        
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        j = i = count = ret = 0
        for n in nums:
            if n%2: count += 1
            if count == k:
                i = j
                while count == k:
                    count -= 1 if nums[j] % 2 else 0
                    j += 1
            ret += j - i
        return ret
            


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        left_pointer = 0
        right_pointer = -1
        count = 0
        odd = 0
        
        while right_pointer < len(nums) - 1:
            right_pointer += 1
            
            if nums[right_pointer] % 2 == 1:
                odd += 1
            
            if odd == k:
                left_side = 1
                right_side = 1
                
                while right_pointer < len(nums) - 1 and nums[right_pointer + 1] % 2 == 0:
                    right_side += 1
                    right_pointer += 1
                    
                while left_pointer <= right_pointer and nums[left_pointer] % 2 == 0:
                    left_side += 1
                    left_pointer += 1
                    
                count += left_side * right_side
                left_pointer += 1
                odd -= 1
                
        return count
    
# def numberOfSubarrays(self, nums: List[int], k: int) -> int:
#     i = count = nice_count = odd_count = 0
#     for j in range(len(nums)):
#         if nums[j] % 2 == 1:
#             odd_count += 1
#             if odd_count == k:
#                 count = 0
#                 while odd_count == k:
#                     if nums[i] % 2 == 1:
#                         odd_count -= 1
#                     i += 1
#                     count += 1
#         nice_count += count

#     return nice_count


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return self.atMost(nums, k) - self.atMost(nums, k - 1)
    
    def atMost(self, nums, k):
        res = left = 0
        
        odds = 0
        
        for right in range(len(nums)):
            if nums[right] % 2 == 1:
                k -= 1
            
            while k < 0:
                if nums[left] % 2 == 1:
                    k += 1
                left += 1
                
            res += right - left + 1
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def at_most(k):
            num_odd=res=i=0
            for j,v in enumerate(nums):
                if v%2 !=0:
                    num_odd+=1
                while num_odd>k:
                    if nums[i]%2==1:
                        num_odd-=1
                    i+=1
                res+=j-i+1
            return res
        
        return at_most(k)-at_most(k-1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        return self.atMost(nums,k) - self.atMost(nums, k-1)
    def atMost(self, nums, k):
        count = {0:0,1:0}
        res = i = 0
        for j in range(len(nums)):
            if nums[j] % 2 == 1:
                k -= 1
            while k < 0:
                if nums[i] % 2 == 1:
                    k += 1
                i += 1
            res += j - i + 1
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # option 1: at most
#         def atMost(A, k):
#             res = 0
#             i = 0
#             for j in range(len(A)):
#                 k -= A[j]%2
#                 while k < 0:
#                     k += A[i]%2
#                     i += 1
#                 res += j - i + 1
#             return res
        
#         return atMost(nums, k) - atMost(nums, k-1)
        
        # option 2: 3 pointers
        res = i = count = 0
        for j in range(len(nums)):
            if nums[j]%2:
                k -= 1
                count = 0
            
            while k == 0:
                k += nums[i]%2
                i += 1
                count += 1
            
            res += count
        return res

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        for i in range(len(nums)):
            if(nums[i]%2 == 0):
                nums[i] = 0
            else:
                nums[i] = 1
        
        pre = [0]
        for c in nums:
            pre.append(pre[-1]+c)
        
        res = 0
        dic = {}
        for c in pre:
            if(c-k in dic):
                res += dic[c-k]
            
            if(c not in dic):
                dic[c] = 1
            else:
                dic[c] += 1
        return res

class Solution:
    def atMostK(self, nums, k):
        start = 0
        end = 0
        count = 0
        for end in range(len(nums)):
            if nums[end] % 2 == 1:
                k -= 1
            while k < 0:
                if nums[start] % 2 == 1:
                    k += 1
                start += 1
            count += end - start + 1
        return count
    
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        if not nums or len(nums) == 0 or k > len(nums):
            return 0
        odds = 0
        return self.atMostK(nums, k) - self.atMostK(nums, k - 1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        d = {0:1}
        s = 0
        count = 0
        for i in range(len(nums)):
            
            nums[i]%=2
            s += nums[i]
            if not s in d:
                d[s]=0
            d[s]+=1
            if s-k in d:
                count += d[s-k]
                
        return count
                
            
        
            
        
        


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        def atMostK(nums, K):
            res = 0
            b=0
            oddCount = 0
            for e in range(len(nums)):
                oddCount += int(nums[e]%2==1)
                
                while oddCount>K:
                    oddCount -= int(nums[b]%2==1)
                    b += 1
                
                res += e-b+1
            
            return res
        
        return atMostK(nums, k) - atMostK(nums, k-1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        def at_most_k(k: int) -> int:
            i, j, odds = 0, 0, 0
            res = 0
            while j < n:
                if nums[j] % 2:
                    odds += 1
                while i <= j and odds > k:
                    if nums[i] % 2:
                        odds -= 1
                    i += 1
                j += 1
                res += j - i
            return res
        
        return at_most_k(k) - at_most_k(k-1)

class Solution:
   def numberOfSubarrays(self, nums: List[int], k: int) -> int:            
    cnt = 0 
    items = [-1]
    for i in range(len(nums)):
        if nums[i] % 2 != 0:
            items.append(i)
    items.append(len(nums))

    for i in range(1, len(items) - k ):
        left = items[i] - items[i - 1]
        right = items[i + k] - items[i + k-1]
        cnt += left * right
    return cnt 



class Window:
    def __init__(self):
        self.odd = 0

    def add(self, value: int):
        if value % 2 == 1:
            self.odd += 1

    def remove(self, value: int):
        if value % 2 == 1:
            self.odd -= 1


class Solution:
    def numberOfSubarrays(self, A: List[int], k: int) -> int:
        window1 = Window()
        window2 = Window()
        left1 = left2 = answer = 0

        for right in A:
            window1.add(right)
            window2.add(right)

            while window1.odd > k:
                window1.remove(A[left1])
                left1 += 1

            while window2.odd >= k:
                window2.remove(A[left2])
                left2 += 1
            answer += left2 - left1
        return answer

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        result=0
        start,count=0,0
        for i in range(len(nums)):
            if nums[i]%2!=0:
                count+=1
            while start<i and count>k:
                if nums[start]%2!=0:
                    count-=1
                start+=1
            if count==k:
                result+=1
            for j in range(start,i):
                if count==k and nums[j]%2==0:
                    result+=1
                else:
                    break
        return result


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        P = [0]
        for n in nums:
            P.append(P[-1] + n % 2)
        
        from collections import Counter
        count = Counter()
        ans = 0
        for p in P:
            ans += count[p]
            count[p + k] += 1
            
        return ans

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = count = l = 0
        
        for num in nums:
            if num & 1:
                k -= 1
                count = 0
                
            while k == 0:
                k += nums[l] & 1
                count += 1
                l += 1
                
            ans += count
            
        return ans
        


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt=collections.Counter()
        cnt[0],odd,res=1,0,0
        for i in nums:
            if i%2==1: odd += 1
            cnt[odd] +=1
            res += cnt[odd-k]
        return res
                


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        
        def atmostK(K):
            res=0
            k=0
            count=collections.Counter()
            for i in range(len(nums)):
                if(nums[i]%2==1): 
                    count[1]+=1
                while(count[1]>K):
                    if(nums[k]%2==1):
                        count[1]-=1
                    k+=1
                res+=i-k+1
            return res
        
        return atmostK(k)-atmostK(k-1)


class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        i = 0
        count = 0
        nice_count = 0 
        odd_count = 0 
        for j in range(len(nums)):
            if nums[j] % 2 == 1:
                odd_count += 1
                count = 0
            while odd_count == k:
                odd_count -=nums[i]%2
                i+=1
                count+=1
            nice_count += count
        return nice_count

from collections import Counter

class Solution:
    def numberOfSubarrays(self, A, k):
        psum = [0]
        for x in map(lambda x: x % 2, A):
            psum.append(psum[-1] + x)
            
        count = Counter(psum)
        return sum(count[p - k] for p in psum)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        nums = [num%2 for num in nums]
        count = 0
        
        indexlist = deque()
        for i in range(len(nums)):
            if nums[i] == 1:
                indexlist.append(i)
        
        #print(indexlist)
        for i in range(len(indexlist)):
            if i != 0:
                left = indexlist[i-1]+1
            else:
                left = 0
                
            if i + k-1 > len(indexlist)-1:
                break
            
            if i + k-1 != len(indexlist) -1:
                right = indexlist[i+k-1+1] -1
            else:
                right = len(nums)-1
                
            leftdis = indexlist[i] - left + 1
            rightdis = right - indexlist[i+k-1] + 1
            print((leftdis, rightdis, left, right))
            count += leftdis * rightdis
        
        return count