Dada una array arr[] , la tarea es contar todos los subconjuntos cuya suma se puede representar como la diferencia de cuadrados de dos números cualesquiera.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 4
Explicación:
Los sub-arreglos requeridos son {1}, {3}, {1, 2} y {2, 3}
Como 1 2 – 0 2 = 1 , 2 2 – 1 2 = 3, 2+3=5=> 3 2 – 2 2 = 5Entrada: array[] = {2, 1, 3, 7}
Salida: 7
Las subarreglas requeridas son:
{1}, {3}, {7}, {2, 1}, {2, 1, 3, 7 }, {1, 3} y {1, 3, 7}
Enfoque: La idea es utilizar el hecho de que el número que es impar o divisible por 4 solo puede representarse como la diferencia de cuadrados de 2 números. A continuación se muestra la ilustración de los pasos:
- Ejecute bucles anidados y verifique para cada subarreglo si la suma se puede escribir como la diferencia de cuadrados de 2 números o no.
- Si la suma de cualquier subarreglo se puede representar como la diferencia del cuadrado de dos números, entonces incremente el conteo de tales subarreglos en 1
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
7
Complejidad temporal: O(N 2 )