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
using System ; class GFG { static int [ ] findSubarrays ( int [ ] a ) { int n = a . Length ; int [ ] freq = new int [ 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 ; } static void countRectangles ( int [ ] a , int [ ] b , int K ) { int n = a . Length ; int m = b . Length ; int [ ] subA = findSubarrays ( a ) ; int [ ] subB = findSubarrays ( b ) ; int total = 0 ; for ( int i = 1 ; i < subA . Length ; i ++ ) { if ( K % i == 0 && ( K / i ) <= m ) { total = total + subA [ i ] * subB [ K / i ] ; } } Console . Write ( total ) ; } public static void Main ( String [ ] args ) { int [ ] a = { 0 , 0 , 1 , 1 } ; int [ ] b = { 1 , 0 , 1 } ; int K = 2 ; countRectangles ( a , b , K ) ; } }