You are given array nums of n elements and integer K, and count the number of subarrays that has k odd numbers.
Example1:
Input:
n = 5
nums = [1,1,2,1,1]
k = 3
Output:
2
Explanation:
There are 2 subarrays with k odds [1,1,2,1] and [1,2,1,1]
Example 2:
Input:
n=3
nums = [2,4,6]
k = 1
Output:
0
Your Task:
You don't have to read input or print anything. Your task is to complete the function countSubarray() which takes the integer n and array nums and integer K as input and returns the count of subarray having k odds number.
Expected Time Complexity: O(n)
Expected Space Complexity: O(n)
Constraint:
1 <= n <= 50000
1 <= nums <= 105
1 <= k <=n

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def countSubarray(self, n, nums, k):

        # Code here

Solutions:
class Solution:

	def countSubarray(self, n, nums, k):
		for i in range(n):
			num = nums[i]
			if num & 1 == 0:
				nums[i] = 0
			else:
				nums[i] = 1
		sum_dict = {0: 1}
		sum = 0
		count = 0
		for num in nums:
			sum += num
			rem = sum - k
			if rem in sum_dict:
				count += sum_dict[rem]
			sum_dict[sum] = sum_dict.get(sum, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def countSubarray(self, n, nums, k):
		m = defaultdict(int)
		m[0] = 1
		ans = 0
		curr = 0
		for i in range(n):
			if nums[i] % 2 == 1:
				curr += 1
			m[curr] += 1
			ans += m[curr - k]
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		nums = [number % 2 for number in nums]
		return self.numberOfSubArraysWithAtMost(n, nums, k) - self.numberOfSubArraysWithAtMost(n, nums, k - 1)

	def numberOfSubArraysWithAtMost(self, n, nums, k):
		(i, ans) = (0, 0)
		count = 0
		for j in range(n):
			count += nums[j]
			while count > k:
				count -= nums[i]
				i += 1
			ans += j - i + 1
		return ans


class Solution:

	def atmost(self, arr, target):
		if target < 0:
			return 0
		cs = 0
		s = 0
		res = 0
		for i in range(len(arr)):
			cs = cs + arr[i]
			while cs > target:
				cs = cs - arr[s]
				s = s + 1
			res = res + i - s + 1
		return res

	def countSubarray(self, n, nums, k):
		for i in range(n):
			if nums[i] % 2 == 0:
				nums[i] = 0
			else:
				nums[i] = 1
		return self.atmost(nums, k) - self.atmost(nums, k - 1)


class Solution:

	def countSubarray(self, n, nums, k):
		for i in range(n):
			nums[i] = nums[i] % 2
		return self.atMost(n, nums, k) - self.atMost(n, nums, k - 1)

	def atMost(self, n, nums, k):
		(i, ans, count) = (0, 0, 0)
		for j in range(n):
			count += nums[j]
			while i <= j and count > k:
				count -= nums[i]
				i += 1
			ans += j - i + 1
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		dic = {0: 1}
		cnt = res = 0
		for (idx, num) in enumerate(nums):
			if num % 2 == 1:
				cnt += 1
			if cnt - k in dic:
				res += dic[cnt - k]
			dic[cnt] = dic.get(cnt, 0) + 1
		return res


class Solution:

	def countSubarray(self, n, nums, k):
		(right, left) = (0, 0)
		ans = 0
		odd_cnt = 0
		ans = 0
		cur_sub_cnt = 0
		for right in range(len(nums)):
			if nums[right] % 2 == 1:
				odd_cnt += 1
				cur_sub_cnt = 0
			while odd_cnt == k:
				if nums[left] % 2 == 1:
					odd_cnt -= 1
				cur_sub_cnt += 1
				left += 1
			ans += cur_sub_cnt
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		count = 0
		left = 0
		right = 0
		odd_count = 0
		while left <= right and right < n:
			if nums[right] % 2 != 0:
				odd_count += 1
			if odd_count > k:
				rc = right - 1
				lc = left
				cr = 0
				cl = 0
				while nums[lc] % 2 == 0:
					cl += 1
					lc += 1
				while nums[rc] % 2 == 0:
					rc -= 1
					cr += 1
				left = lc + 1
				odd_count -= 1
				count += (cr + 1) * (cl + 1)
			if odd_count == k and right == n - 1:
				rc = right
				lc = left
				cr = 0
				cl = 0
				while nums[lc] % 2 == 0:
					cl += 1
					lc += 1
				while nums[rc] % 2 == 0:
					rc -= 1
					cr += 1
				count += (cr + 1) * (cl + 1)
			right += 1
		return count


class Solution:

	def countSubarray(self, n, nums, k):
		for i in range(0, n):
			if nums[i] % 2 == 1:
				nums[i] = 1
			else:
				nums[i] = 0
		return self.helper(nums, k) - self.helper(nums, k - 1)

	def helper(self, nums, target):
		if target < 0:
			return 0
		left = 0
		ans = 0
		n = len(nums)
		su = 0
		for right in range(0, n):
			su += nums[right]
			while su > target:
				su -= nums[left]
				left += 1
			ans += right - left + 1
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		answer = 0
		count = 0
		tmp = 0
		for i in range(n):
			nums[i] = nums[i] % 2
		i = 0
		for j in range(n):
			count += nums[j]
			if count == k:
				tmp = 0
				while i <= j and count == k:
					count -= nums[i]
					i += 1
					tmp += 1
			answer += tmp
		return answer


class Solution:

	def countSubarray(self, n, nums, k):
		sum1 = 0
		count = 0
		d = {}
		for i in range(n):
			if nums[i] % 2 != 0:
				nums[i] = 1
			else:
				nums[i] = 0
		for i in range(n):
			sum1 = sum1 + nums[i]
			if sum1 == k:
				count = count + 1
			if sum1 - k in d:
				count = count + d[sum1 - k]
			if sum1 in d:
				d[sum1] += 1
			else:
				d[sum1] = 1
		return count


class Solution:

	def countSubarray(self, n, nums, k):
		ans = 0
		odd = 0
		j = 0
		i = 0
		temp = 0
		while i < n:
			if nums[i] % 2 != 0:
				odd += 1
				temp = 0
			while odd == k:
				temp += 1
				if nums[j] % 2 != 0:
					odd -= 1
				j += 1
			ans += temp
			i += 1
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		count = 0
		count_odd = {}
		res = 0
		for i in range(len(nums)):
			if nums[i] % 2:
				count += 1
			if count == k:
				res += 1
			if count_odd.get(count - k, 0):
				res += count_odd[count - k]
			count_odd[count] = 1 + count_odd.get(count, 0)
		return res


class Solution:

	def solve(self, arr, n, k):
		ans = 0
		(i, j) = (0, 0)
		c = 0
		while j < n:
			if arr[j] % 2 != 0:
				c += 1
			while c > k:
				if arr[i] % 2 != 0:
					c -= 1
				i += 1
			ans += j - i + 1
			j += 1
		return ans

	def countSubarray(self, n, arr, k):
		return self.solve(arr, n, k) - self.solve(arr, n, k - 1)


class Solution:

	def countSubarray(self, n, nums, k):
		for i in range(len(nums)):
			if nums[i] % 2 != 0:
				nums[i] = 1
			else:
				nums[i] = 0
		c = 0
		s = 0
		d = {}
		for i in range(len(nums)):
			s += nums[i]
			if s == k:
				c += 1
			if s - k in d:
				c += d[s - k]
			if s not in d:
				d[s] = 1
			else:
				d[s] += 1
		return c


class Solution:

	def countSubarray(self, n, nums, k):
		l = 0
		r = 0
		c = 0
		odd = 0
		t = 0
		while r < n:
			if nums[r] % 2 != 0:
				odd += 1
				t = 0
			while odd == k:
				t += 1
				if nums[l] % 2 != 0:
					odd -= 1
				l += 1
			c += t
			r += 1
		return c


from collections import defaultdict

class Solution:

	def countSubarray(self, n, arr, target):
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				arr[i] = 0
			else:
				arr[i] = 1
		dct = defaultdict(lambda : 0)
		summ = 0
		count = 0
		for i in range(0, len(arr)):
			summ += arr[i]
			if summ == target:
				count += 1
			if summ - target in dct:
				count += dct[summ - target]
			dct[summ] += 1
		return count


class Solution:

	def countSubarray(self, n, nums, k):

		def total(count):
			if count < 0:
				return 0
			res = 0
			i = 0
			for j in range(n):
				if nums[j] % 2 != 0:
					count -= 1
				while count < 0:
					if nums[i] % 2 != 0:
						count += 1
					i += 1
				res += j - i + 1
			return res
		return total(k) - total(k - 1)


class Solution:

	def countSubarray(self, n, nums, k):
		remainders = []
		rem = 0
		num_subarray = 0
		for num in nums:
			rem += num % 2
			remainders.append(rem)
		prefix = {0: 1}
		for remainder in remainders:
			if remainder - k in prefix:
				num_subarray += prefix[remainder - k]
			if remainder not in prefix:
				prefix[remainder] = 1
			else:
				prefix[remainder] += 1
		return num_subarray


class Solution:

	def countSubarray(self, n, nums, k):
		ans = 0
		(i, j) = (0, 0)
		(res, od) = (0, 0)
		while j < n:
			if nums[j] % 2 != 0:
				od += 1
				res = 0
			while od == k:
				res += 1
				if nums[i] % 2 != 0:
					od -= 1
				i += 1
			ans += res
			j += 1
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		c = {}
		c[0] = 1
		res = 0
		total = 0
		for num in nums:
			if num % 2:
				total += 1
			if total - k in c:
				res += c[total - k]
			if total in c:
				c[total] += 1
			else:
				c[total] = 1
		return res


class Solution:

	def atmost(self, n, arr, k):
		start = end = answer = count = 0
		while end < n:
			if arr[end] & 1 == 1:
				count += 1
			while count > k and start < n:
				if arr[start] & 1 == 1:
					count += -1
				start += 1
			answer += end - start + 1
			end += 1
		return answer

	def countSubarray(self, n, arr, k):
		return self.atmost(n, arr, k) - self.atmost(n, arr, k - 1)


class Solution:

	def countSubarray(self, n, nums, k):
		l = []
		s = 0
		for i in nums:
			s += i % 2
			l.append(s)
		d = {0: 1}
		c = 0
		for i in l:
			if i - k in d:
				c += d[i - k]
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		return c


class Solution:

	def countSubarray(self, n, nums, k):
		p = count = res = 0
		for i in range(len(nums)):
			if nums[i] & 1:
				k -= 1
				count = 0
			while k == 0:
				k += nums[p] & 1
				p += 1
				count += 1
			res += count
		return res


class Solution:

	def countSubarray(self, n, nums, k):
		for i in range(len(nums)):
			if nums[i] % 2 == 0:
				nums[i] = 0
			else:
				nums[i] = 1
		s = 0
		p = 0
		h = {0: 1}
		for j in nums:
			p += j
			if p - k in h:
				s += h[p - k]
			if p in h:
				h[p] += 1
			else:
				h[p] = 1
		return s


class Solution:

	def countSubarray(self, n, nums, k):
		l = count = res = no = 0
		for r in range(n):
			if nums[r] % 2 == 0:
				res += count
			else:
				count = 0
				no += 1
				while l <= r and no >= k:
					if no == k:
						count += 1
					if nums[l] % 2 != 0:
						no += -1
					l += 1
				res += count
		return res


class Solution:

	def countSubarray(self, n, nums, goal):

		def binarysubwithsum():
			mapi = [0] * (len(nums) + 1)
			sum_ = 0
			mapi[0] = 1
			result = 0
			for num in nums:
				sum_ += num & 1
				if sum_ - goal >= 0:
					result += mapi[sum_ - goal]
				mapi[sum_] += 1
			return result
		return binarysubwithsum()


class Solution:

	def countSubarray(self, n, nums, k):
		mp = {}
		mp[0] = 1
		for i in range(len(nums)):
			nums[i] = nums[i] % 2
		(ans, sum) = (0, 0)
		for i in range(len(nums)):
			sum += nums[i]
			if sum - k in mp:
				ans += mp[sum - k]
			if sum in mp:
				mp[sum] += 1
			else:
				mp[sum] = 1
		return ans


from collections import Counter

class Solution:

	def countSubarray(self, n, nums, k):
		counter = Counter()
		odd = 0
		counter[0] += 1
		for num in nums:
			if num % 2 == 1:
				odd += 1
			counter[odd] += 1
		j = k
		i = 0
		ans = 0
		while j <= odd:
			ans += counter[j] * counter[i]
			j += 1
			i += 1
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		n = len(nums)
		for i in range(n):
			if nums[i] % 2 == 0:
				nums[i] = 0
			else:
				nums[i] = 1
		s = 0
		ans = 0
		hm = {}
		for i in range(n):
			s += nums[i]
			if s == k:
				ans += 1
			if s - k in hm:
				ans += hm[s - k]
			if s in hm:
				hm[s] += 1
			else:
				hm[s] = 1
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		(l, r) = (0, 0)
		count = 0
		odd = 0
		res = 0
		while r < n:
			if nums[r] % 2 != 0:
				odd += 1
				count = 0
			while odd == k:
				count += 1
				if nums[l] % 2 != 0:
					odd -= 1
				l += 1
			res += count
			r += 1
		return res


class Solution:

	def countSubarray(self, n, nums, k):
		for i in range(0, n):
			if nums[i] % 2 != 0:
				nums[i] = 1
			else:
				nums[i] = 0
		d = {}
		(ans, temp) = (0, 0)
		for i in nums:
			temp += i
			if temp == k:
				ans += 1
			if temp - k in d:
				ans += d[temp - k]
			d[temp] = 1 + d.get(temp, 0)
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		left = 0
		odd_count = 0
		nice_count = 0
		count = 0
		ans = 0
		for i in range(n):
			if nums[i] % 2 != 0:
				odd_count += 1
				count = 0
			while odd_count == k:
				odd_count -= nums[left] % 2
				left += 1
				count += 1
			nice_count += count
		return nice_count


class Solution:

	def count(self, s, n, k):
		j = 0
		c = 0
		d = 0
		for i in range(n):
			if s[i] % 2:
				d += 1
			while d > k:
				if s[j] % 2:
					d -= 1
				j += 1
			c += i - j
		return c

	def countSubarray(self, n, nums, k):
		return self.count(nums, n, k) - self.count(nums, n, k - 1)


class Solution:

	def countSubarray(self, n, nums, k):
		j = 0
		ans = 0
		temp = 0
		for i in range(n):
			if nums[i] % 2 == 1:
				k -= 1
				temp = 0
			while k == 0:
				temp += 1
				if nums[j] % 2 == 1:
					k += 1
				j += 1
			ans += temp
		return ans


class Solution:

	def countSubarray(self, n, nums, k):
		count = 0
		dic = {}
		sum = 0
		for (i, num) in enumerate(nums):
			if num % 2 == 0:
				nums[i] = 0
			else:
				nums[i] = 1
		for num in nums:
			sum += num
			if sum == k:
				count += 1
			if sum - k in dic:
				count += dic[sum - k]
			if sum not in dic:
				dic[sum] = 1
			else:
				dic[sum] += 1
		return count


class Solution:

	def countSubarray(self, n, nums, k):
		(start, end) = (0, 0)
		count = 0
		a = 0
		ans = 0
		while end < len(nums):
			if nums[end] % 2 != 0:
				count += 1
				a = 0
			while count == k:
				a += 1
				count -= nums[start] & 1
				start += 1
			ans += a
			end += 1
		return ans