Given an array arr[] containing N elements that contain both positive and negative elements, the task is to find the total number of contiguous subsequences whose product can be expressed as the difference of the square of two integers.
Examples:
Input: arr[] = {1, 0, 2, 4, 5}
Output: 14
Explanation:
There are 14 subsequences whose product can be expressed as the difference of the square of two integers.
They are: {1}, {0}, {4}, {5}, {1, 0}, {1, 0, 2}, {1, 0, 2, 4}, {1, 0, 2, 4, 5}, {0, 2}, {0, 2, 4}, {0, 2, 4, 5}, {2, 4}, {2, 4, 5}, {4, 5}
The product of all the subsequences can be expressed as the difference of two squares. For example:
1 -> 1^2 – 0^2
0 -> 1^2 – 1^2
4 -> 2^2 – 0^2
5 -> 3^2 – 2^2
8 -> 3^2 – 1^2 …… and so on.Input: arr[] = {-2, -7, 8, 9}
Output: 8
Explanation:
There are 8 subsequences whose product can be expressed as the difference of the square of two integers.
They are: {-7}, {8}, {9}, {-2, -7, 8}, {-2, -7, 8, 9}, {-7, 8}, {-7, 8, 9}, {8, 9}
The product of all the subsequences can be expressed as the difference of two squares. For example:
-7 -> 3^2 – 4^2
8 -> 3^2 – 1^2
9 -> 3^2 – 0^2
112 -> 11^2 – 3^2 …… and so on.
Naive approach: The naive approach for this problem is to generate all the contiguous subsequences and compute its product and simply check if that number can be expressed as the difference of two squares or not.
Below is the implementation of the above approach:
C++
// C++ implementation to count the // number of contiguous subsequences // whose product can be expressed as // the square of difference of two integers #include <bits/stdc++.h> using namespace std; // Function to count the number // of contiguous subsequences // whose product can be expressed // as square of difference of two integers int CntcontSubs( int a[], int n) { int c = 0, d = 0, i, sum = 1, j; // Iterating through the array for (i = 0; i < n; i++) { // Check if that number can be // expressed as the square of // difference of two numbers if (a[i] % 2 != 0 || a[i] % 4 == 0) d++; // Variable to compute the product sum = a[i]; // Finding the remaining subsequences for (j = i + 1; j < n; j++) { sum = sum * a[j]; // Check if that number can be // expressed as the square of // difference of two numbers if (sum % 2 != 0 || sum % 4 == 0) c++; } sum = 1; } // Return the number of subsequences return c + d; } // Driver code int main() { int arr[] = { 5, 4, 2, 9, 8 }; int n = sizeof (arr) / sizeof (arr[0]); cout << CntcontSubs(arr, n); return 0; } |
Java
// Java implementation to count the // number of contiguous subsequences // whose product can be expressed as // the square of difference of two integers class GFG{ // Function to count the number // of contiguous subsequences // whose product can be expressed // as square of difference of two integers static int CntcontSubs( int a[], int n) { int c = 0 , d = 0 , i, sum = 1 , j; // Iterating through the array for (i = 0 ; i < n; i++) { // Check if that number can be // expressed as the square of // difference of two numbers if (a[i] % 2 != 0 || a[i] % 4 == 0 ) d++; // Variable to compute the product sum = a[i]; // Finding the remaining subsequences for (j = i + 1 ; j < n; j++) { sum = sum * a[j]; // Check if that number can be // expressed as the square of // difference of two numbers if (sum % 2 != 0 || sum % 4 == 0 ) c++; } sum = 1 ; } // Return the number of subsequences return c + d; } // Driver code public static void main(String[] args) { int arr[] = { 5 , 4 , 2 , 9 , 8 }; int n = arr.length; System.out.print(CntcontSubs(arr, n)); } } // This code contributed by PrinciRaj1992 |
Python3
# Python3 implementation to count the # number of contiguous subsequences # whose product can be expressed as # the square of difference of two integers # Function to count the number # of contiguous subsequences # whose product can be expressed # as square of difference of two integers def CntcontSubs(a, n): c = 0 d = 0 sum = 1 # Iterating through the array for i in range (n): # Check if that number can be # expressed as the square of # difference of two numbers if (a[i] % 2 ! = 0 or a[i] % 4 = = 0 ): d + = 1 # Variable to compute the product sum = a[i] # Finding the remaining subsequences for j in range (i + 1 , n): sum = sum * a[j] # Check if that number can be # expressed as the square of # difference of two numbers if ( sum % 2 ! = 0 or sum % 4 = = 0 ): c + = 1 sum = 1 # Return the number of subsequences return c + d # Driver code if __name__ = = '__main__' : arr = [ 5 , 4 , 2 , 9 , 8 ] n = len (arr) print (CntcontSubs(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to count the // number of contiguous subsequences // whose product can be expressed as // the square of difference of two integers using System; class GFG{ // Function to count the number // of contiguous subsequences // whose product can be expressed // as square of difference of two integers static int CntcontSubs( int []a, int n) { int c = 0, d = 0, i, sum = 1, j; // Iterating through the array for (i = 0; i < n; i++) { // Check if that number can be // expressed as the square of // difference of two numbers if (a[i] % 2 != 0 || a[i] % 4 == 0) d++; // Variable to compute the product sum = a[i]; // Finding the remaining subsequences for (j = i + 1; j < n; j++) { sum = sum * a[j]; // Check if that number can be // expressed as the square of // difference of two numbers if (sum % 2 != 0 || sum % 4 == 0) c++; } sum = 1; } // Return the number of subsequences return c + d; } // Driver code static void Main() { int []arr = { 5, 4, 2, 9, 8 }; int n = arr.Length; Console.Write(CntcontSubs(arr, n)); } } // This code is contributed by grand_master |
Javascript
<script> // Javascript implementation to count the // number of contiguous subsequences // whose product can be expressed as // the square of difference of two integers // Function to count the number // of contiguous subsequences // whose product can be expressed // as square of difference of two integers function CntcontSubs(a, n) { let c = 0, d = 0, i, sum = 1, j; // Iterating through the array for (i = 0; i < n; i++) { // Check if that number can be // expressed as the square of // difference of two numbers if (a[i] % 2 != 0 || a[i] % 4 == 0) d++; // Variable to compute the product sum = a[i]; // Finding the remaining subsequences for (j = i + 1; j < n; j++) { sum = sum * a[j]; // Check if that number can be // expressed as the square of // difference of two numbers if (sum % 2 != 0 || sum % 4 == 0) c++; } sum = 1; } // Return the number of subsequences return c + d; } // Driver code let arr = [ 5, 4, 2, 9, 8 ]; let n = arr.length; document.write(CntcontSubs(arr, n)); </script> |
13
Time Complexity: O(N2) where N is the length of the array.
Auxiliary Space: O(1)
Efficient Approach: The idea lies behind the identity that a number cannot be expressed as the difference of two squares if it gives a remainder 2 when divided by 4. Therefore, the idea is to find all the subsequences which yield a product of 2 and subtract these from the total possible subsequences for the array. The total number of contiguous subsequences can be obtained by the formula: (N * (N + 1)) / 2
- If the array contains the element 0, then the product of all the subsequences containing this element becomes 0. Therefore, all those subsequences can be expressed as the difference of two squares.
- If any element gives the remainder 2 when the number is divided by 4, then all the subsequences up to the nearest 2 or 0 have to be avoided because the remainder becomes 4 when a 2 is encountered and it becomes 0 when a 0 is encountered.
Example:
- Let arr[] = {6, 5, 13, 10, 4, 8, 14, 17}.
- We compute the remainders when the elements are divided by 4. So, {2, 1, 1, 2, 0, 0, 2, 1} are the remainders of the given array.
- Here we get the remainder 2 at the index 1, 4, 7. Let’s observe the 2 at the first index.
- The following are the subsequences of the remainder array {2}, {2, 1}, {2, 1, 1}, {2, 1, 1, 2}, {2, 1, 1, 2, 0} … {2, 1, 1, 2, 0, 0, 2, 1}.
- The product of the subsequences is {2, 2, 2, 4, 0 …. 0}.
- So we get the product as 2 from index 1 to index 3. Hence, the total contiguous subsequences from index 1 to index 3 whose product is 2 are 2 (i.e.) [index-3 – index-1].
- So, clearly, we find the nearest index of the element 2 or 0 and ignore all the subsequences until this index.
Below is the implementation of the above approach:
C++
// C++ implementation to count all the // contiguous subsequences whose // product is expressed as the square // of the difference of two integers #include <bits/stdc++.h> using namespace std; // Function to count all the // contiguous subsequences whose // product is expressed as the square // of the difference of two integers int CntcontSubs( int a[], int n) { int prod = 1; // Creating vectors to store // the remainders and the // subsequences vector<pair< int , int > > vect; vect.push_back(make_pair(0, 2)); vector< int > two, zero; // Iterating through the array for ( int i = 0; i < n; i++) { // Finding the remainder when the // element is divided by 4 a[i] = a[i] % 4; // Bringing all the elements in // the range [0, 3] if (a[i] < 0) a[i] = a[i] + 4; // If the remainder is 2, store // the index of the if (a[i] == 2) two.push_back(i + 1); // If the remainder is 2, store // the index of the 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)); // Finding the total number of subsequences int total = (n * (n + 1)) / 2; // If there are no numbers which // yield the remainder 2 if (two.empty()) return total; else { int sum = 0; int pos1 = -1, pos2 = -1, pos3 = -1; int sz = vect.size(); // Iterating through the vector for ( int i = 1; i + 1 < sz; i++) { // If the element is 2, find the nearest // 2 or 0 and find the number of // elements between them if (vect[i].second == 2) { sum += (vect[i].first - vect[i - 1].first) * (vect[i + 1].first - vect[i].first) - 1; } } // Returning the count return total - sum - two.size(); } } // Driver code int main() { int a[] = { 5, 4, 2, 9, 8 }; int n = sizeof (a) / sizeof (a[0]); cout << CntcontSubs(a, n); return 0; } |
Java
// Java implementation to count all the // contiguous subsequences whose // product is expressed as the square // of the difference of two integers import java.util.*; class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to count all the // contiguous subsequences whose // product is expressed as the square // of the difference of two integers static int CntcontSubs( int a[], int n) { int prod = 1 ; // Creating vectors to store // the remainders and the // subsequences Vector<pair> vect = new Vector<pair>(); vect.add( new pair( 0 , 2 )); Vector<Integer> two = new Vector<Integer>(); Vector<Integer> zero = new Vector<Integer>(); // Iterating through the array for ( int i = 0 ; i < n; i++) { // Finding the remainder when the // element is divided by 4 a[i] = a[i] % 4 ; // Bringing all the elements in // the range [0, 3] if (a[i] < 0 ) a[i] = a[i] + 4 ; // If the remainder is 2, store // the index of the if (a[i] == 2 ) two.add(i + 1 ); // If the remainder is 2, store // the index of the 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 )); // Finding the total number of subsequences int total = (n * (n + 1 )) / 2 ; // If there are no numbers which // yield the remainder 2 if (two.isEmpty()) return total; else { int sum = 0 ; int pos1 = - 1 , pos2 = - 1 , pos3 = - 1 ; int sz = vect.size(); // Iterating through the vector for ( int i = 1 ; i + 1 < sz; i++) { // If the element is 2, find the nearest // 2 or 0 and find the number of // elements between them 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 ; } } // Returning the count return total - sum - two.size(); } } // Driver code public static void main(String[] args) { int a[] = { 5 , 4 , 2 , 9 , 8 }; int n = a.length; System.out.print(CntcontSubs(a, n)); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 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 def CntcontSubs(a, n): prod = 1 # Creating vectors to store # the remainders and the # subsequences vect = [] vect.append(( 0 , 2 )) two, zero = [], [] # Iterating through the array for i in range (n): # Finding the remainder when the # element is divided by 4 a[i] = a[i] % 4 # Bringing all the elements in # the range [0, 3] if (a[i] < 0 ): a[i] = a[i] + 4 # If the remainder is 2, store # the index of the if (a[i] = = 2 ): two.append(i + 1 ) # If the remainder is 2, store # the index of the if (a[i] = = 0 ): zero.append(i + 1 ) if (a[i] = = 0 or a[i] = = 2 ): vect.append((i + 1 , a[i])) vect.append((n + 1 , 2 )) # Finding the total number of subsequences total = (n * (n + 1 )) / / 2 # If there are no numbers which # yield the remainder 2 if ( len (two) = = 0 ): return total else : Sum = 0 pos1, pos2, pos3 = - 1 , - 1 , - 1 sz = len (vect) # Iterating through the vector for i in range ( 1 , sz - 1 ): # If the element is 2, find the # nearest 2 or 0 and find the # number of elements between them if (vect[i][ 1 ] = = 2 ) : Sum + = ((vect[i][ 0 ] - vect[i - 1 ][ 0 ]) * (vect[i + 1 ][ 0 ] - vect[i][ 0 ]) - 1 ) # Returning the count return (total - Sum - len (two)) # Driver Code a = [ 5 , 4 , 2 , 9 , 8 ] n = len (a) print (CntcontSubs(a, n)) # This code is contributed by divyeshrabadiya07 |
C#
// C# implementation to count all the // contiguous subsequences whose // product is expressed as the square // of the difference of two integers using System; using System.Collections.Generic; class GFG{ class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to count all the // contiguous subsequences whose // product is expressed as the square // of the difference of two integers static int CntcontSubs( int []a, int n) { // Creating vectors to store // the remainders and the // subsequences List<pair> vect = new List<pair>(); vect.Add( new pair(0, 2)); List< int > two = new List< int >(); List< int > zero = new List< int >(); // Iterating through the array for ( int i = 0; i < n; i++) { // Finding the remainder when the // element is divided by 4 a[i] = a[i] % 4; // Bringing all the elements in // the range [0, 3] if (a[i] < 0) a[i] = a[i] + 4; // If the remainder is 2, store // the index of the if (a[i] == 2) two.Add(i + 1); // If the remainder is 2, store // the index of the 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)); // Finding the total number of subsequences int total = (n * (n + 1)) / 2; // If there are no numbers which // yield the remainder 2 if (two.Count == 0) return total; else { int sum = 0; int sz = vect.Count; // Iterating through the vector for ( int i = 1; i + 1 < sz; i++) { // If the element is 2, find the nearest // 2 or 0 and find the number of // elements between them if (vect[i].second == 2) { sum += (vect[i].first - vect[i - 1].first) * (vect[i + 1].first - vect[i].first) - 1; } } // Returning the count return total - sum - two.Count; } } // Driver code public static void Main(String[] args) { int []a = { 5, 4, 2, 9, 8 }; int n = a.Length; Console.Write(CntcontSubs(a, n)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript 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 function CntcontSubs(a,n) { let prod = 1; // Creating vectors to store // the remainders and the // subsequences let vect = []; vect.push([0, 2]); let two = []; let zero = []; // Iterating through the array for (let i = 0; i < n; i++) { // Finding the remainder when the // element is divided by 4 a[i] = a[i] % 4; // Bringing all the elements in // the range [0, 3] if (a[i] < 0) a[i] = a[i] + 4; // If the remainder is 2, store // the index of the if (a[i] == 2) two.push(i + 1); // If the remainder is 2, store // the index of the if (a[i] == 0) zero.push(i + 1); if (a[i] == 0 || a[i] == 2) vect.push([i + 1, a[i]]); } vect.push([n + 1, 2]); // Finding the total number of subsequences let total = Math.floor((n * (n + 1)) / 2); // If there are no numbers which // yield the remainder 2 if (two.length==0) return total; else { let sum = 0; let pos1 = -1, pos2 = -1, pos3 = -1; let sz = vect.length; // Iterating through the vector for (let i = 1; i + 1 < sz; i++) { // If the element is 2, find the nearest // 2 or 0 and find the number of // elements between them if (vect[i][1] == 2) { sum += (vect[i][0] - vect[i-1][0]) * (vect[i+1][0] - vect[i][0]) - 1; } } // Returning the count return total - sum - two.length; } } // Driver code let a = [5, 4, 2, 9, 8]; let n = a.length; document.write(CntcontSubs(a, n)); // This code is contributed by patel2127 </script> |
13
Time Complexity: O(N) where N is the length of the array.
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!