Count of Rectangles with area K made up of only 1 s from given Binary Arrays | 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
def findSubarrays ( a ) : NEW_LINE INDENT n = len ( a ) NEW_LINE freq = [ 0 ] * ( n + 1 ) NEW_LINE count = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( a [ i ] == 0 ) : NEW_LINE INDENT if ( count == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT else : NEW_LINE INDENT value = count NEW_LINE for j in range ( 1 , count + 1 ) : NEW_LINE INDENT freq [ j ] += value NEW_LINE value -= 1 NEW_LINE DEDENT count = 0 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT if ( count > 0 ) : NEW_LINE INDENT value = count NEW_LINE for j in range ( 1 , count + 1 ) : NEW_LINE INDENT freq [ j ] += value NEW_LINE value -= 1 NEW_LINE DEDENT DEDENT return freq NEW_LINE DEDENT def countRectangles ( a , b , K ) : NEW_LINE INDENT n = len ( a ) NEW_LINE m = len ( b ) NEW_LINE subA = [ ] NEW_LINE subA = findSubarrays ( a ) NEW_LINE subB = [ ] NEW_LINE subB = findSubarrays ( b ) NEW_LINE total = 0 NEW_LINE for i in range ( 1 , len ( subA ) ) : NEW_LINE INDENT if ( K % i == 0 and ( K // i ) <= m ) : NEW_LINE INDENT total = total + subA [ i ] * subB [ K // i ] NEW_LINE DEDENT DEDENT print ( total ) NEW_LINE DEDENT a = [ 0 , 0 , 1 , 1 ] NEW_LINE b = [ 1 , 0 , 1 ] NEW_LINE K = 2 NEW_LINE countRectangles ( a , b , K ) NEW_LINE