Day 96 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/count-subarray-with-k-odds/1

Count Subarray with k odds

Difficulty: Medium Accuracy: 53.77%

You are given an array arr[] of positive integers and an integer k. You have to count the number of subarrays that contain exactly k odd numbers.
Examples:
Input: arr[] = [2, 5, 6, 9], k = 2
Output: 2
Explanation: There are 2 subarrays with 2 odds: [2, 5, 6, 9] and [5, 6, 9].
Input: arr[] = [2, 2, 5, 6, 9, 2, 11], k = 2
Output: 8
Explanation: There are 8 subarrays with 2 odds: [2, 2, 5, 6, 9], [2, 5, 6, 9], [5, 6, 9], [2, 2, 5, 6, 9, 2], [2, 5, 6, 9, 2], [5, 6, 9, 2], [6, 9, 2, 11] and [9, 2, 11].
Constraint:
1 ≤ k ≤ arr.size() ≤ 105
1 ≤ arr[i] ≤ 109

Solution:
class Solution:
def countSubarrays(self, arr, k):
mp = {0: 1}
prefix = 0
ans = 0
for x in arr:
prefix += (x & 1)
if prefix - k in mp:
ans += mp[prefix - k]
mp[prefix] = mp.get(prefix, 0) + 1
return ans