Number of Nice Subarray✨|| Easiest 🤩|| Fastest🚀🚀||Beats 99% 😤😤||Prefix Count🪛
\n\n\n# Intuition\nThe problem revolves around identifying subarrays that contain exactly k odd numbers. The intuition is to maintain a running count of odd num
![Screenshot 2024-06-22 081735.png](https://assets.leetcode.com/users/images/1cd72501-de52-418c-b92d-c953e487f76c_1719024569.532309.png)\n\n\n# Intuition\nThe problem revolves around identifying subarrays that contain exactly k odd numbers. The intuition is to maintain a running count of odd numbers encountered as we iterate through the array. By doing so, we can determine if a valid subarray ends at the current position by checking how many previous subarrays (or prefixes) have a specific number of odd numbers. This approach leverages the concept of prefix sums, commonly used in various subarray problems. In essence, if we know how many subarrays have a certain number of odd numbers up to a given point, we can quickly determine how many subarrays ending at the current position have the desired number of odd numbers.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Initialization: We start by initializing an array count_odds to keep track of the number of subarrays (prefixes) that contain a certain number of odd numbers. We set count_odds[0] = 1 to handle the case where the current prefix has exactly k odd numbers.\n\n2. Iterating through the array: We use a variable t to maintain the cumulative count of odd numbers encountered so far. For each element in the array, we update t by adding 1 if the element is odd (using num & 1).\n\n3. Counting valid subarrays: For each element, we check if there is a valid subarray ending at the current position by verifying if t - k is non-negative. If it is, it means there are count_odds[t - k] subarrays that can form a "nice" subarray with exactly k odd numbers ending at the current position. We add this count to subarray_count.\n\n4. Updating count_odds: Finally, we increment count_odds[t] to record that there is now one more prefix with t odd numbers.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n### Java \n\n```\nclass Solution {\n    public int numberOfSubarrays(int[] nums, int k) {\n        int[] count_odds = new int[nums.length + 1];\n        count_odds[0] = 1;  //For the time when sum - k is 0\n        int subarray_count = 0;\n        int t = 0;\n        for(int num : nums)\n        {\n            t += num & 1;  //If it is odd then num & 1 will be 1 , if even then 0\n            if(t - k >= 0)\n                subarray_count += count_odds[t - k];\n            \n            count_odds[t]++;\n        }\n        return subarray_count;\n    }\n}\n```\n\n### Python\n\n```\nclass Solution:\n    def numberOfSubarrays(self, nums, k):\n        count_odds = [0] * (len(nums) + 1)\n        count_odds[0] = 1  # For the case when t - k == 0\n        subarray_count = 0\n        t = 0\n        for num in nums:\n            t += num % 2  # If the number is odd, num % 2 will be 1, otherwise 0\n            if t - k >= 0:\n                subarray_count += count_odds[t - k]\n            \n            count_odds[t] += 1\n        return subarray_count\n```\n\n![Screenshot 2024-06-11 062532.png](https://assets.leetcode.com/users/images/f45c4322-50b1-4592-bd98-1b7e1b0803b6_1719024556.0081851.png)\n
['Array', 'Hash Table', 'Math', 'Prefix Sum', 'Java']