Number of ways to select equal sized subarrays from two arrays having atleast K equal pairs of elements | C ++ implementation to count the number of ways to select equal sized subarrays such that they have atleast K common elements ; 2D prefix sum for submatrix sum query for matrix ; Function to find the prefix sum of the matrix from i and j ; Function to count the number of ways to select equal sized subarrays such that they have atleast K common elements ; Combining the two arrays ; Calculating the 2D prefix sum ; iterating through all the elements of matrix and considering them to be the bottom right ; applying binary search over side length ; if sum of this submatrix >= k then new search space will be [ low , mid ] ; else new search space will be [ mid + 1 , high ] ; Adding the total submatrices ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int prefix_2D [ 2005 ] [ 2005 ] ; int subMatrixSum ( int i , int j , int len ) { return prefix_2D [ i ] [ j ] - prefix_2D [ i ] [ j - len ] - prefix_2D [ i - len ] [ j ] + prefix_2D [ i - len ] [ j - len ] ; } int numberOfWays ( int a [ ] , int b [ ] , int n , int m , int k ) { for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { if ( a [ i - 1 ] == b [ j - 1 ] ) prefix_2D [ i ] [ j ] = 1 ; else prefix_2D [ i ] [ j ] = 0 ; } } for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { prefix_2D [ i ] [ j ] += prefix_2D [ i ] [ j - 1 ] ; } } for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { prefix_2D [ i ] [ j ] += prefix_2D [ i - 1 ] [ j ] ; } } int answer = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { int low = 1 ; int high = min ( i , j ) ; while ( low < high ) { int mid = ( low + high ) >> 1 ; if ( subMatrixSum ( i , j , mid ) >= k ) { high = mid ; } else { low = mid + 1 ; } } if ( subMatrixSum ( i , j , low ) >= k ) { answer += ( min ( i , j ) - low + 1 ) ; } } } return answer ; } int main ( ) { int N = 2 , M = 3 ; int A [ N ] = { 1 , 2 } ; int B [ M ] = { 1 , 2 , 3 } ; int K = 1 ; cout << numberOfWays ( A , B , N , M , K ) ; return 0 ; }