Subsequences of size three in an array whose sum is divisible by m | O ( M ^ 2 ) time complexity PHP program to find count of subsequences of size three divisible by M . ; Storing frequencies of all remainders when divided by M . ; including i and j in the sum rem calculate the remainder required to make the sum divisible by M ; if the required number is less than j , we skip as we have already calculated for that value before . As j here starts with i and rem is less than j . ; if satisfies the first case . ; if satisfies the second case ; if satisfies the third case ; Driver code
< ? php function countSubSeq ( $ A , $ N , $ M ) { $ ans = 0 ; $ h = array_fill ( 0 , $ M , 0 ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { $ A [ $ i ] = $ A [ $ i ] % $ M ; $ h [ $ A [ $ i ] ] ++ ; } for ( $ i = 0 ; $ i < $ M ; $ i ++ ) { for ( $ j = $ i ; $ j < $ M ; $ j ++ ) { $ rem = ( $ M - ( $ i + $ j ) % $ M ) % $ M ; if ( $ rem < $ j ) continue ; if ( $ i == $ j && $ rem == $ j ) $ ans += $ h [ $ i ] * ( $ h [ $ i ] - 1 ) * ( $ h [ $ i ] - 2 ) / 6 ; else if ( $ i == $ j ) $ ans += $ h [ $ i ] * ( $ h [ $ i ] - 1 ) * $ h [ $ rem ] / 2 ; else if ( $ i == $ rem ) $ ans += $ h [ $ i ] * ( $ h [ $ i ] - 1 ) * $ h [ $ j ] / 2 ; else if ( $ rem == $ j ) $ ans += $ h [ $ j ] * ( $ h [ $ j ] - 1 ) * $ h [ $ i ] / 2 ; else $ ans = $ ans + $ h [ $ i ] * $ h [ $ j ] * $ h [ $ rem ] ; } } return $ ans ; } $ M = 3 ; $ A = array ( 1 , 2 , 4 , 3 ) ; $ N = count ( $ A ) ; echo countSubSeq ( $ A , $ N , $ M ) ; ? >