Count of Rectangles with area K made up of only 1 s from given Binary Arrays | C ++ Program to implement the above approach ; Function to find the subarrays of all possible lengths made up of only 1 s ; Stores the frequency of the subarrays ; Check if the previous value was also 0 ; If the previous value was 1 ; Find the subarrays of each size from 1 to count ; If A [ ] is of the form ... .111 ; Function to find the count of all possible rectangles ; Size of each of the arrays ; Stores the count of subarrays of each size consisting of only 1 s from array A [ ] ; Stores the count of subarrays of each size consisting of only 1 s from array B [ ] ; Iterating over all subarrays consisting of only 1 s in A [ ] ; If i is a factor of K , then there is a subarray of size K / i in B [ ] ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > findSubarrays ( vector < int > & a ) { int n = a . size ( ) ; vector < int > freq ( n + 1 ) ; int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( a [ i ] == 0 ) { if ( count == 0 ) continue ; else { int value = count ; for ( int j = 1 ; j <= count ; j ++ ) { freq [ j ] += value ; value -- ; } count = 0 ; } } else count ++ ; } if ( count > 0 ) { int value = count ; for ( int j = 1 ; j <= count ; j ++ ) { freq [ j ] += value ; value -- ; } } return freq ; } void countRectangles ( vector < int > & a , vector < int > & b , int K ) { int n = a . size ( ) ; int m = b . size ( ) ; vector < int > subA = findSubarrays ( a ) ; vector < int > subB = findSubarrays ( b ) ; int total = 0 ; for ( int i = 1 ; i < subA . size ( ) ; i ++ ) { if ( K % i == 0 and ( K / i ) <= m ) { total = total + subA [ i ] * subB [ K / i ] ; } } cout << total ; } int main ( ) { vector < int > a = { 0 , 0 , 1 , 1 } ; vector < int > b = { 1 , 0 , 1 } ; int K = 2 ; countRectangles ( a , b , K ) ; return 0 ; }