Count subarrays with sum as difference of squares of two numbers
Given an array arr[], the task is to count all sub-array whose sum can be represented as the difference of squares of any two numbers.
Examples:
Input: arr[] = {1, 2, 3}
Output: 4
Explanation:
Required sub-arrays are {1}, {3}, {1, 2} and {2, 3}
As 12 – 02 = 1, 22 – 12 = 3, 2+3=5=> 32 – 22 = 5Input: arr[] = {2, 1, 3, 7}
Output: 7
Required sub-arrays are –
{1}, {3}, {7}, {2, 1}, {2, 1, 3, 7}, {1, 3} and {1, 3, 7}
Approach: The idea is to use the fact that the number which is odd or divisible by 4 can only be represented as the difference of squares of 2 numbers. Below is the illustration of the steps:
- Run nested loops and check for every sub-array whether sum can be written as the difference of squares of 2 numbers or not.
- If the sum of any subarray can be represented as the difference of the square of two numbers then increment the count of such subarrays by 1
Below is the implementation of the above approach:
C++
// C++ implementation to count the // subarray which can be represented // as the difference of two square // of two numbers #include <bits/stdc++.h> using namespace std; #define ll long long // Function to count sub-arrays whose // sum can be represented as difference // of squares of 2 numbers int countSubarray( int * arr, int n) { int count = 0; for ( int i = 0; i < n; i++) { // Count the elements that // are odd and divisible by 4 if (arr[i] % 2 != 0 || arr[i] % 4 == 0) count++; // Declare a variable to store sum ll sum = arr[i]; for ( int j = i + 1; j < n; j++) { // Calculate sum of // current subarray sum += arr[j]; if (sum % 2 != 0 || sum % 4 == 0) count++; } } return count; } // Driver Code int main() { int arr[] = { 2, 1, 3, 7 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countSubarray(arr, n) << endl; return 0; } |
Java
// Java implementation to count the // subarray which can be represented // as the difference of two square // of two numbers import java.util.*; class GFG { // Function to count sub-arrays whose // sum can be represented as difference // of squares of 2 numbers static int countSubarray( int [] arr, int n) { int count = 0 ; for ( int i = 0 ; i < n; i++) { // Count the elements that // are odd and divisible by 4 if (arr[i] % 2 != 0 || arr[i] % 4 == 0 ) count++; // Declare a variable to store sum long sum = arr[i]; for ( int j = i + 1 ; j < n; j++) { // Calculate sum of // current subarray sum += arr[j]; if (sum % 2 != 0 || sum % 4 == 0 ) count++; } } return count; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 1 , 3 , 7 }; int n = arr.length; System.out.println(countSubarray(arr, n)); } } |
Python3
# Python implementation to # count the sub-arrays whose # sum can be represented as # difference of square of two # numbers # Function to count sub-arrays whose # sum can be represented as # difference of squares of 2 numbers def countSubarray(arr, n): count = 0 for i in range (n): # Count the elements that # are odd or divisible by 4 if arr[i] % 2 ! = 0 or arr[i] % 4 = = 0 : count + = 1 # Declare a variable to store sum tot = arr[i] for j in range (i + 1 , n): # Calculate sum of # current subarray tot + = arr[j] if tot % 2 ! = 0 or tot % 4 = = 0 : count + = 1 return count # Driver Code if __name__ = = "__main__" : arr = [ 2 , 1 , 3 , 7 ] n = len (arr) print (countSubarray(arr, n)) |
C#
// C# implementation to count the // subarray which can be represented // as the difference of two square // of two numbers using System; class GFG { // Function to count sub-arrays whose // sum can be represented as difference // of squares of 2 numbers static int countSubarray( int [] arr, int n) { int count = 0; for ( int i = 0; i < n; i++) { // Count the elements that // are odd and divisible by 4 if (arr[i] % 2 != 0 || arr[i] % 4 == 0) count++; // Declare a variable to store sum long sum = arr[i]; for ( int j = i + 1; j < n; j++) { // Calculate sum of // current subarray sum += arr[j]; if (sum % 2 != 0 || sum % 4 == 0) count++; } } return count; } // Driver Code public static void Main() { int [] arr = { 2, 1, 3, 7 }; int n = arr.Length; Console.WriteLine(countSubarray(arr, n)); } } |
PHP
<?php // PHP implementation to count the // subarray which can be represented // as the difference of two square // of two numbers // Function to count sub-arrays whose // sum is divisible by K function countSubarray( $arr , $n ) { $count =0; for ( $i =0; $i < $n ; $i ++) { // Count the elements that // are odd and divisible by 4 if ( $arr [ $i ]%2!=0 || $arr [ $i ]%4==0) $count ++; // Declare a variable to store sum $sum = $arr [ $i ]; for ( $j = $i +1; $j < $n ; $j ++) { // Calculate sum of // current subarray $sum += $arr [ $j ]; if ( $sum %2!=0 || $sum %4==0) $count ++; } } return $count ; } // Driver code $arr = array ( 2, 1, 3, 7 ); $n = count ( $arr ); echo countSubarray( $arr , $n ); ?> |
Javascript
<script> // Javascript implementation to count the // subarray which can be represented // as the difference of two square // of two numbers // Function to count sub-arrays whose // sum can be represented as difference // of squares of 2 numbers function countSubarray(arr, n) { var count = 0; for ( var i = 0; i < n; i++) { // Count the elements that // are odd and divisible by 4 if (arr[i] % 2 != 0 || arr[i] % 4 == 0) count++; // Declare a variable to store sum var sum = arr[i]; for ( var j = i + 1; j < n; j++) { // Calculate sum of // current subarray sum += arr[j]; if (sum % 2 != 0 || sum % 4 == 0) count++; } } return count; } // Driver code var arr = [ 2, 1, 3, 7 ]; var n = arr.length; document.write(countSubarray(arr, n)); // This code is contributed by shivanisinghss2110 </script> |
Output:
7
Time Complexity: O(N2)