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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Mathematics

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:
		edge = []
		res = 0
		count = 0
		for i in nums:
			if i % 2:
				edge.append(count + 1)
				count = 0
			else:
				count += 1
		edge.append(count + 1)
		if len(edge) - 1 < k:
			return 0
		else:
			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)
		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:

		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)
		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:
					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)
			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
			if odds - k in seen:
				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:

		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:
		return self.sol1(nums, k) - self.sol1(nums, k - 1)

	def sol1(self, nums, k):
		start = 0
		odds = 0
		res = 0
		for end in range(len(nums)):
			odds += nums[end] & 1
			while odds > k:
				odds -= nums[start] & 1
				start += 1
			res += end - start + 1
		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:
				odds += 1
				count = 0
			while odds >= k:
				if nums[start] & 1:
					odds -= 1
				start += 1
				count += 1
			res += count
		return res


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:
		num_odd_numbers = 0
		foo = 0
		left = 0
		right = 0
		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:
				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: 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)
		for i in range(len(oddList) - k):
			noOfNiceSubArrays += (oddList[i] + 1) * (oddList[i + k] + 1)
		return noOfNiceSubArrays


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
		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
				j = beg - 1
				left_count = 0
				while j >= 0:
					if nums[j] % 2 == 0:
						left_count += 1
					else:
						break
					j -= 1
				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:
		(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


from collections import defaultdict

class Solution:

	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:
		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


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)


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.append(1)
		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:
		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
		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
			count = count + start_len * end_len
			i = i + 1
		return count


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)
		if k > n:
			return 0
		ans = 0
		p1 = p2 = p3 = p4 = -1
		while p4 < n:
			p2 += 1
			while p2 < n and nums[p2] % 2 == 0:
				p2 += 1
				if p2 == n:
					return ans
			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
			p4 = p3 + 1
			while p4 < n:
				if nums[p4] % 2 == 1:
					break
				p4 += 1
			ans += (p2 - p1) * (p4 - p3)
			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:
				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:
		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
		num_odd = 0
		seen = defaultdict(int)
		seen[0] = 1
		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:
		count = 0
		dic = defaultdict(int)
		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:
				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


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:
				k += nums[l]
				l += 1
				tmp += 1
			ans += tmp
		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
		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


class Solution:

	def numberOfSubarrays(self, nums: List[int], k: int) -> int:
		ans = 0
		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()
		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


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:

		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)


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:

		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


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:
		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:

		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 len(nums) == 0:
			return 0
		preprocess = [0] * (len(nums) + 1)
		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
		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:
					k += nums[start_ptr] % 2
					start_ptr += 1
				result += end_ptr - start_ptr + 1
			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:
		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


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:
		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 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)


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)
		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