Dada una array arr[] , la tarea es contar todos los subarreglos cuya suma se puede dividir como la diferencia de los cuadrados de dos enteros.
Ejemplos:
Entrada: arr[] = {1, 3, 5}
Salida: 6
Explicación:
Hay seis subarreglos que se pueden formar a partir del arreglo cuya suma se puede dividir como la diferencia de cuadrados de dos enteros. Ellos son:
Suma del subarreglo {1} = 1 = 1 2 – 0 2
Suma del subarreglo {3} = 3 = 2 2 – 1 2
Suma del subarreglo {5} = 5 = 3 2 – 2 2
Suma de el subarreglo {1, 3} = 4 = 2 2 – 0 2
Suma del subarreglo {3, 5} = 8 = 3 2 – 1 2
Suma del subarreglo {1, 3, 5} = 9 = 5 2 – 4 2
Entrada:array[] = {1, 2, 3, 4, 5}
Salida: 11
Enfoque: Para resolver este problema, es necesario hacer una observación. Cualquier número puede representarse como la diferencia de dos cuadrados excepto aquellos que pueden representarse en la forma ((4 * N) + 2) donde N es un número entero. Por lo tanto, se pueden seguir los siguientes pasos para calcular la respuesta:
- Iterar sobre el arreglo para encontrar todos los subarreglos posibles del arreglo dado.
- Si un número K se puede expresar como ((4 * N) + 2) donde N es un número entero, entonces K + 2 es siempre un múltiplo de 4.
- Por lo tanto, para cada suma del subarreglo K, compruebe si (K + 2) es múltiplo de 4 o no.
- Si lo es, entonces ese valor particular no puede expresarse como la diferencia de los cuadrados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count all the non-contiguous
// subarrays whose sum can be split
// as the difference of the squares
#include <bits/stdc++.h>
using namespace std;
// Function to count all the non-contiguous
// subarrays whose sum can be split
// as the difference of the squares
int Solve(int arr[], int n)
{
int temp = 0, count = 0;
// Loop to iterate over all the possible
// subsequences of the array
for (int i = 0; i < n; i++) {
temp = 0;
for (int j = i; j < n; j++) {
// Finding the sum of all the
// possible subsequences
temp += arr[j];
// Condition to check whether
// the number can be split
// as difference of squares
if ((temp + 2) % 4 != 0)
count++;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int N = sizeof(arr) / sizeof(int);
cout << Solve(arr, N);
return 0;
}
Java
// Java program to count all the
// non-contiguous subarrays whose
// sum can be split as the
// difference of the squares
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to count all the non-contiguous
// subarrays whose sum can be split
// as the difference of the squares
static int Solve(int arr[], int n)
{
int temp = 0, count = 0;
// Loop to iterate over all the possible
// subsequences of the array
for(int i = 0; i < n; i++)
{
temp = 0;
for(int j = i; j < n; j++)
{
// Finding the sum of all the
// possible subsequences
temp += arr[j];
// Condition to check whether
// the number can be split
// as difference of squares
if ((temp + 2) % 4 != 0)
count++;
}
}
return count;
}
// Driver Code
public static void main(String [] args)
{
int arr[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int N = arr.length;
System.out.println(Solve(arr, N));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to count all the non-contiguous # subarrays whose sum can be split # as the difference of the squares # Function to count all the non-contiguous # subarrays whose sum can be split # as the difference of the squares def Solve(arr, n): temp = 0; count = 0; # Loop to iterate over all the possible # subsequences of the array for i in range(0, n): temp = 0; for j in range(i, n): # Finding the sum of all the # possible subsequences temp = temp + arr[j]; # Condition to check whether # the number can be split # as difference of squares if ((temp + 2) % 4 != 0): count += 1; return count; # Driver code arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; N = len(arr); print(Solve(arr, N)); # This code is contributed by Code_Mech
C#
// C# program to count all the
// non-contiguous subarrays whose
// sum can be split as the
// difference of the squares
using System;
class GFG{
// Function to count all the
// non-contiguous subarrays whose
// sum can be split as the
// difference of the squares
static int Solve(int []arr, int n)
{
int temp = 0, count = 0;
// Loop to iterate over all
// the possible subsequences
// of the array
for(int i = 0; i < n; i++)
{
temp = 0;
for(int j = i; j < n; j++)
{
// Finding the sum of all the
// possible subsequences
temp += arr[j];
// Condition to check whether
// the number can be split
// as difference of squares
if ((temp + 2) % 4 != 0)
count++;
}
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int N = arr.Length;
Console.Write(Solve(arr, N));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to count all the non-contiguous
// subarrays whose sum can be split
// as the difference of the squares
// Function to count all the non-contiguous
// subarrays whose sum can be split
// as the difference of the squares
function Solve(arr, n)
{
let temp = 0, count = 0;
// Loop to iterate over all the possible
// subsequences of the array
for (let i = 0; i < n; i++) {
temp = 0;
for (let j = i; j < n; j++) {
// Finding the sum of all the
// possible subsequences
temp += arr[j];
// Condition to check whether
// the number can be split
// as difference of squares
if ((temp + 2) % 4 != 0)
count++;
}
}
return count;
}
// Driver code
let arr = [ 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 ];
let N = arr.length;
document.write(Solve(arr, N));
// This code is contributed by souravmahato348.
</script>
40
Complejidad de tiempo: O(N) 2 donde N es el tamaño de la array
Publicación traducida automáticamente
Artículo escrito por epistler_999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA