Count of subsequences whose product is a difference of square of two integers | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int CntcontSubs ( int a [ ] , int n ) { int prod = 1 ; Vector < pair > vect = new Vector < pair > ( ) ; vect . add ( new pair ( 0 , 2 ) ) ; Vector < Integer > two = new Vector < Integer > ( ) ; Vector < Integer > zero = new Vector < Integer > ( ) ; 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 . add ( i + 1 ) ; if ( a [ i ] == 0 ) zero . add ( i + 1 ) ; if ( a [ i ] == 0 a [ i ] == 2 ) vect . add ( new pair ( i + 1 , a [ i ] ) ) ; } vect . add ( new pair ( n + 1 , 2 ) ) ; int total = ( n * ( n + 1 ) ) / 2 ; if ( two . isEmpty ( ) ) 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 . get ( i ) . second == 2 ) { sum += ( vect . get ( i ) . first - vect . get ( i - 1 ) . first ) * ( vect . get ( i + 1 ) . first - vect . get ( i ) . first ) - 1 ; } } return total - sum - two . size ( ) ; } } public static void main ( String [ ] args ) { int a [ ] = { 5 , 4 , 2 , 9 , 8 } ; int n = a . length ; System . out . print ( CntcontSubs ( a , n ) ) ; } }