hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Count Subarrays
Problem: Count Subarrays
Problem Link: www.codingninjas.com/codestudio/problems/count-subarrays-consisting-of-only-0-s-and-only-1-s-in-a-binary-array_1262154
Approach:
Declared a variable ans = 0.
Count the appearance of array elements.
Check for contiguous 0 and 1.
For X amount of contiguous zeroes or ones, calculated the sub-array using the equation, X * ( X + 1) / 2.
Added the counting into the ans.
Returned ans.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++]
#include <bits/stdc++.h>
int numberofSubarrays(vector<int> & arr, int n){
int count_contiguous = 0;
long long ans = 0;
for(int i=0; i<n; i++){
if(i == 0 || arr[i] == arr[i-1]){
count_contiguous++;
}
else if(arr[i] != arr[i-1]){
ans += (long long)(count_contiguous * (count_contiguous + 1)) >> 1;
count_contiguous = 1;
}
}
ans += (long long)(count_contiguous * (count_contiguous + 1)) >> 1;
return ans;
}