✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS -Prefix Sum -Interview Solution
\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n **I
![Screenshot 2024-06-22 061620.png](https://assets.leetcode.com/users/images/c80c4521-769c-4e92-be6d-d559d69b7e88_1719017662.3639119.png)\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n<!-- **If you want a video for this question please write in the comments** -->\n\nhttps://youtu.be/fORIuIT_KDQ\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2250 Subscribers*\n*Current Subscribers: 2197*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires counting the number of continuous subarrays with exactly `k` odd numbers. To achieve this, we can use a prefix sum approach. The key idea is to keep track of the number of odd numbers encountered so far while iterating through the array, and use this information to count subarrays with the desired property efficiently.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialize Variables**:\n   - `n`: Length of the input array `nums`.\n   - `cnt`: An array to keep track of the count of prefix sums (number of odd numbers encountered).\n   - `cnt[0]`: Set to 1 initially, since a prefix sum of 0 (no odd numbers encountered) occurs once by default.\n   - `ans`: Variable to store the final result (number of nice subarrays).\n   - `t`: Variable to store the current count of odd numbers while iterating through the array.\n\n2. **Iterate Through the Array**:\n   - For each element `v` in `nums`, update the count of odd numbers (`t`) encountered so far. This is done by checking if `v` is odd using `v & 1`.\n   - Check if there exists a prefix sum `t - k` (i.e., a previous state where there were `t - k` odd numbers). If so, add the count of such prefix sums to `ans`.\n   - Increment the count of the current prefix sum (`t`) in the `cnt` array.\n\n3. **Return the Result**:\n   - After iterating through the entire array, `ans` will contain the number of nice subarrays.\n\n\n# Complexity\n- **Time Complexity**: The solution iterates through the array once and performs constant time operations in each iteration. Thus, the time complexity is \\(O(n)\\), where \\(n\\) is the length of the array.\n- **Space Complexity**: The space complexity is \\(O(n)\\) due to the additional `cnt` array used to store the count of prefix sums.\n\n\n# Step by Step Explanation\n\n\n### Example\n\nLet\'s use an example to explain the approach:  \n`nums = [1, 1, 2, 1, 1]`, `k = 3`\n\n| Index | `nums[i]` | Odd Count (`t`) | `cnt` Array (Updated) | `t - k` | Count of `t - k` in `cnt` | Result (`ans`) |\n|-------|-----------|-----------------|-----------------------|---------|---------------------------|----------------|\n| 0     | 1         | 1               | [1, 1, 0, 0, 0, 0]    | -2      | 0                         | 0              |\n| 1     | 1         | 2               | [1, 1, 1, 0, 0, 0]    | -1      | 0                         | 0              |\n| 2     | 2         | 2               | [1, 1, 2, 0, 0, 0]    | -1      | 0                         | 0              |\n| 3     | 1         | 3               | [1, 1, 2, 1, 0, 0]    | 0       | 1                         | 1              |\n| 4     | 1         | 4               | [1, 1, 2, 1, 1, 0]    | 1       | 1                         | 2              |\n\n### Steps Explained with Example\n\n1. **Initialization**:\n   - `cnt = [1, 0, 0, 0, 0, 0]`\n   - `ans = 0`\n   - `t = 0`\n\n2. **Iteration**:\n   - **Index 0**: \n     - `nums[0] = 1` (odd)\n     - `t = 1` (1 odd number)\n     - Update `cnt`: `cnt[1] += 1` \u2192 `cnt = [1, 1, 0, 0, 0, 0]`\n     - `t - k = 1 - 3 = -2` (invalid)\n     - `ans = 0`\n   \n   - **Index 1**:\n     - `nums[1] = 1` (odd)\n     - `t = 2` (2 odd numbers)\n     - Update `cnt`: `cnt[2] += 1` \u2192 `cnt = [1, 1, 1, 0, 0, 0]`\n     - `t - k = 2 - 3 = -1` (invalid)\n     - `ans = 0`\n   \n   - **Index 2**:\n     - `nums[2] = 2` (even)\n     - `t = 2` (no change in odd count)\n     - Update `cnt`: `cnt[2] += 1` \u2192 `cnt = [1, 1, 2, 0, 0, 0]`\n     - `t - k = 2 - 3 = -1` (invalid)\n     - `ans = 0`\n   \n   - **Index 3**:\n     - `nums[3] = 1` (odd)\n     - `t = 3` (3 odd numbers)\n     - Update `cnt`: `cnt[3] += 1` \u2192 `cnt = [1, 1, 2, 1, 0, 0]`\n     - `t - k = 3 - 3 = 0`\n     - `cnt[0] = 1` (one valid prefix sum)\n     - `ans += 1` \u2192 `ans = 1`\n   \n   - **Index 4**:\n     - `nums[4] = 1` (odd)\n     - `t = 4` (4 odd numbers)\n     - Update `cnt`: `cnt[4] += 1` \u2192 `cnt = [1, 1, 2, 1, 1, 0]`\n     - `t - k = 4 - 3 = 1`\n     - `cnt[1] = 1` (one valid prefix sum)\n     - `ans += 1` \u2192 `ans = 2`\n\n### Final Answer\nThe number of nice subarrays is `2`.\n\n---\n\n\n\n# Code\n```java []\nclass Solution {\n    public int numberOfSubarrays(int[] nums, int k) {\n        int n = nums.length;\n        int[] cnt = new int[n + 1];\n        cnt[0] = 1;\n        int ans = 0, t = 0;\n        for (int v : nums) {\n            t += v & 1;\n            if (t - k >= 0) {\n                ans += cnt[t - k];\n            }\n            cnt[t]++;\n        }\n        return ans;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<int> cnt(n + 1, 0);\n        cnt[0] = 1;\n        int ans = 0, t = 0;\n        for (int v : nums) {\n            t += v & 1;\n            if (t - k >= 0) {\n                ans += cnt[t - k];\n            }\n            cnt[t]++;\n        }\n        return ans;\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def numberOfSubarrays(self, nums, k):\n        n = len(nums)\n        cnt = [0] * (n + 1)\n        cnt[0] = 1\n        ans = 0\n        t = 0\n        for v in nums:\n            t += v & 1\n            if t - k >= 0:\n                ans += cnt[t - k]\n            cnt[t] += 1\n        return ans\n        \n```\n```JavaScript []\nvar numberOfSubarrays = function(nums, k) {\n    let n = nums.length;\n    let cnt = new Array(n + 1).fill(0);\n    cnt[0] = 1;\n    let ans = 0, t = 0;\n    for (let v of nums) {\n        t += v & 1;\n        if (t - k >= 0) {\n            ans += cnt[t - k];\n        }\n        cnt[t]++;\n    }\n    return ans;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/1e88c30d-1fcc-4e7c-8ef5-bc480fcc4d24_1719017644.1184938.png)\n
['Array', 'Hash Table', 'Math', 'Sliding Window', 'Python', 'C++', 'Java', 'JavaScript']