Count of subsequences whose product is a difference of square of two integers | C ++ implementation to count all the contiguous subsequences whose product is expressed as the square of the difference 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int CntcontSubs ( int a [ ] , int n ) { int prod = 1 ; vector < pair < int , int > > vect ; vect . push_back ( make_pair ( 0 , 2 ) ) ; vector < int > two , zero ; for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = a [ i ] % 4 ; if ( a [ i ] < 0 ) a [ i ] = a [ i ] + 4 ; if ( a [ i ] == 2 ) two . push_back ( i + 1 ) ; if ( a [ i ] == 0 ) zero . push_back ( i + 1 ) ; if ( a [ i ] == 0 a [ i ] == 2 ) vect . push_back ( make_pair ( i + 1 , a [ i ] ) ) ; } vect . push_back ( make_pair ( n + 1 , 2 ) ) ; int total = ( n * ( n + 1 ) ) / 2 ; if ( two . empty ( ) ) return total ; else { int sum = 0 ; int pos1 = -1 , pos2 = -1 , pos3 = -1 ; int sz = vect . size ( ) ; for ( int i = 1 ; i + 1 < sz ; i ++ ) { if ( vect [ i ] . second == 2 ) { sum += ( vect [ i ] . first - vect [ i - 1 ] . first ) * ( vect [ i + 1 ] . first - vect [ i ] . first ) - 1 ; } } return total - sum - two . size ( ) ; } } int main ( ) { int a [ ] = { 5 , 4 , 2 , 9 , 8 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << CntcontSubs ( a , n ) ; return 0 ; }