C++ Sliding Window Solution + Probability Rule O(N)
Runtime: 112 ms, faster than 93.17% of C++ online submissions for Count Number of Nice Subarrays.\nMemory Usage: 67.5 MB, less than 91.98% of C++ online submiss
Runtime: 112 ms, faster than 93.17% of C++ online submissions for Count Number of Nice Subarrays.\nMemory Usage: 67.5 MB, less than 91.98% of C++ online submissions for Count Number of Nice Subarrays.\n\n```\nInorder to solve the problem we can easily find the main subarray containing K odd numbers using Sliding\nWindow approach. Here main subarray means the subarray which has window such as all left most values\nof first odd number are even if possible and all right most values of last odd number are even if possible\ncause there can be exactly K odd numbers and this main subarray will get the subarrays where all odd\nnumbers of the window wil be present. So, we expand window in each step and shrink window if odd count >K. \nWhen odd count == K, we have to find the main subarray and so we expand the window as long as there\nis no new odd number. Now we need the possible subarrays from this main subarray where al odd numbers\nwill be present. For calculating the number of such possible subarrays we can consider the subarry from the\nfirst to last occurence of odd number as a single number X. Then we have to count the number of even\nnumbers EL at the left of X and the number of even numbers ER at the right of X cause they will make the\npossible subarrays from main subarray. \nFor the current main subarray the possible subarray count = (EL +1) * (ER+1)\n```\n\n```\nThis equation comes from the Independent Probability Rule: P(AB) = P(A) * P(B)\nFor example given array : [a,b,c,d,e] and X = c then the number of possible subarray where X exists are,\nNo of way of taking or not taking element from the left of X = EL + 1\nNo of way of taking or not taking element from the right of X = ER + 1\nSo, total possible subarrays with element X = (EL + 1) * (ER + 1) cause here taking element from left and\nright of element X in the subarray is Independent.\nFor  [a,b,c,d,e] and X = c => Subarray count = (2+1) * (2+1) = 3\n{a,b,c}, {b,c},{c}, {a,b,c,d},{b,c,d},{a,b,c,d,e},{b,c,d,e},{c,d},{c,d,e}\n\nSo using above formula we can count the total subarray from a main subarray and sum up the count of \nall main subarrays in the given array and get the result.\n\nExample Input: nums = [2,2,1,2,1,2,2,1,2,2], k = 2,  Output: 15 Below is the simulation of this example\n```\n\n![image](https://assets.leetcode.com/users/images/93861dec-986d-45f7-89e8-d79b938a0c7e_1626024085.1761098.png)\n\n```\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n\n        int n = nums.size();\n\n        // total number of calid subarray\n        int res = 0;\n        \n        // count the odd numbers in the window\n        int cnt = 0;\n        \n        // first and last pointer of sliding window\n        int i = 0;\n        int j = 0;\n        while(j<n)\n        {\n            // update count of the odd number in window\n            if((nums[j++]&1)==1)cnt++;            \n            \n            // shrink window until odd number count == k\n            while(cnt>k)if((nums[i++]&1)==1)cnt--;      \n            \n            // if odd number count == k then we found our main subarray\n            if(cnt==k)\n            {\n                int lc = 0, rc = 0;\n                \n                // shrink window from left till any odd number found\n                // means, count number of even number at the left of first odd number in window, EL\n                while(j<n && (nums[j]&1)==0)j++,rc++;\n\n                // expand window to right till any odd number found\n                // means, count number of even number at the right of last odd number in window, ER\n                while(i<n && (nums[i]&1)==0)i++,lc++;\n                \n                // based on probability formula the total possible subarray inclusing all odd numbers\n                // of the main subarray window is (EL + 1) * (ER + 1)\n                res+= ((lc+1) * (rc+1));\n            }\n        }\n        \n        return res;\n    }\n};\n```\n\n\n
['Array', 'C', 'Sliding Window', 'Probability and Statistics']