Count of subsequences whose product is a difference of square of two integers | Function to count all the contiguous subsequences whose product is expressed as the square of the difference of two integers ; Creating vectors to store the remainders and the subsequences ; Iterating through the array ; Finding the remainder when the element is divided by 4 ; Bringing all the elements in the range [ 0 , 3 ] ; If the remainder is 2 , store the index of the ; If the remainder is 2 , store the index of the ; Finding the total number of subsequences ; If there are no numbers which yield the remainder 2 ; Iterating through the vector ; If the element is 2 , find the nearest 2 or 0 and find the number of elements between them ; Returning the count ; Driver Code
def CntcontSubs ( a , n ) : NEW_LINE INDENT prod = 1 NEW_LINE vect = [ ] NEW_LINE vect . append ( ( 0 , 2 ) ) NEW_LINE two , zero = [ ] , [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT a [ i ] = a [ i ] % 4 NEW_LINE if ( a [ i ] < 0 ) : NEW_LINE INDENT a [ i ] = a [ i ] + 4 NEW_LINE DEDENT if ( a [ i ] == 2 ) : NEW_LINE INDENT two . append ( i + 1 ) NEW_LINE DEDENT if ( a [ i ] == 0 ) : NEW_LINE INDENT zero . append ( i + 1 ) NEW_LINE DEDENT if ( a [ i ] == 0 or a [ i ] == 2 ) : NEW_LINE INDENT vect . append ( ( i + 1 , a [ i ] ) ) NEW_LINE DEDENT DEDENT vect . append ( ( n + 1 , 2 ) ) NEW_LINE total = ( n * ( n + 1 ) ) // 2 NEW_LINE if ( len ( two ) == 0 ) : NEW_LINE INDENT return total NEW_LINE DEDENT else : NEW_LINE INDENT Sum = 0 NEW_LINE pos1 , pos2 , pos3 = - 1 , - 1 , - 1 NEW_LINE sz = len ( vect ) NEW_LINE for i in range ( 1 , sz - 1 ) : NEW_LINE INDENT if ( vect [ i ] [ 1 ] == 2 ) : NEW_LINE INDENT Sum += ( ( vect [ i ] [ 0 ] - vect [ i - 1 ] [ 0 ] ) * ( vect [ i + 1 ] [ 0 ] - vect [ i ] [ 0 ] ) - 1 ) NEW_LINE DEDENT DEDENT return ( total - Sum - len ( two ) ) NEW_LINE DEDENT DEDENT a = [ 5 , 4 , 2 , 9 , 8 ] NEW_LINE n = len ( a ) NEW_LINE print ( CntcontSubs ( a , n ) ) NEW_LINE