Dadas las consultas Q en forma de array 2D arr[][] cuyas filas consisten en dos números L y R que significan el rango [L, R], la tarea es encontrar la suma de todos los cuadrados perfectos que se encuentran en este rango.
Ejemplos:
Entrada: Q = 2, arr[][] = {{4, 9}, {4, 16}}
Salida: 13 29
Explicación:
Del 4 al 9: solo el 4 y el 9 son cuadrados perfectos. Por tanto, 4 + 9 = 13.
Del 4 al 16: 4, 9 y 16 son los cuadrados perfectos. Por lo tanto, 4 + 9 + 16 = 29.
Entrada: Q = 4, arr[][] = {{1, 10}, {1, 100}, {2, 25}, {4, 50}}
Salida: 14 385 54 139
Enfoque: la idea es usar una array de suma de prefijos . La suma de todos los cuadrados se calcula previamente y se almacena en una array pref[] para que cada consulta se pueda responder en tiempo O(1). Cada índice ‘i’ en la array pref[] representa la suma de cuadrados perfectos desde 1 hasta ese número. Por lo tanto, la suma de cuadrados perfectos del rango dado ‘L’ a ‘R’ se puede encontrar de la siguiente manera:
sum = pref[R] - pref[L - 1]
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the sum of all
// perfect squares in the given range
#include <bits/stdc++.h>
#define ll int
using namespace std;
// Array to precompute the sum of squares
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
long long pref[100010];
// Function to check if a number is
// a perfect square or not
int isPerfectSquare(long long int x)
{
// Find floating point value of
// square root of x.
long double sr = sqrt(x);
// If square root is an integer
return ((sr - floor(sr)) == 0) ? x : 0;
}
// Function to precompute the perfect
// squares upto 100000.
void compute()
{
for (int i = 1; i <= 100000; ++i) {
pref[i] = pref[i - 1]
+ isPerfectSquare(i);
}
}
// Function to print the sum for each query
void printSum(int L, int R)
{
int sum = pref[R] - pref[L - 1];
cout << sum << " ";
}
// Driver code
int main()
{
// To calculate the precompute function
compute();
int Q = 4;
int arr[][2] = { { 1, 10 },
{ 1, 100 },
{ 2, 25 },
{ 4, 50 } };
// Calling the printSum function
// for every query
for (int i = 0; i < Q; i++) {
printSum(arr[i][0], arr[i][1]);
}
return 0;
}
Java
// Java program to find the sum of all
// perfect squares in the given range
class GFG
{
// Array to precompute the sum of squares
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
static int []pref = new int[100010];
// Function to check if a number is
// a perfect square or not
static int isPerfectSquare(int x)
{
// Find floating point value of
// square root of x.
double sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0) ? x : 0;
}
// Function to precompute the perfect
// squares upto 100000.
static void compute()
{
for (int i = 1; i <= 100000; ++i)
{
pref[i] = pref[i - 1]
+ isPerfectSquare(i);
}
}
// Function to print the sum for each query
static void printSum(int L, int R)
{
int sum = pref[R] - pref[L - 1];
System.out.print(sum+ " ");
}
// Driver code
public static void main(String[] args)
{
// To calculate the precompute function
compute();
int Q = 4;
int arr[][] = { { 1, 10 },
{ 1, 100 },
{ 2, 25 },
{ 4, 50 } };
// Calling the printSum function
// for every query
for (int i = 0; i < Q; i++)
{
printSum(arr[i][0], arr[i][1]);
}
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find the sum of all # perfect squares in the given range from math import sqrt, floor # Array to precompute the sum of squares # from 1 to 100010 so that for every # query, the answer can be returned in O(1). pref = [0]*100010; # Function to check if a number is # a perfect square or not def isPerfectSquare(x) : # Find floating point value of # square root of x. sr = sqrt(x); # If square root is an integer rslt = x if (sr - floor(sr) == 0) else 0; return rslt; # Function to precompute the perfect # squares upto 100000. def compute() : for i in range(1 , 100001) : pref[i] = pref[i - 1] + isPerfectSquare(i); # Function to print the sum for each query def printSum( L, R) : sum = pref[R] - pref[L - 1]; print(sum ,end= " "); # Driver code if __name__ == "__main__" : # To calculate the precompute function compute(); Q = 4; arr = [ [ 1, 10 ], [ 1, 100 ], [ 2, 25 ], [ 4, 50 ] ]; # Calling the printSum function # for every query for i in range(Q) : printSum(arr[i][0], arr[i][1]); # This code is contributed by AnkitRai01
C#
// C# program to find the sum of all
// perfect squares in the given range
using System;
class GFG
{
// Array to precompute the sum of squares
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
static int []pref = new int[100010];
// Function to check if a number is
// a perfect square or not
static int isPerfectSquare(int x)
{
// Find floating point value of
// square root of x.
double sr = Math.Sqrt(x);
// If square root is an integer
return ((sr - Math.Floor(sr)) == 0) ? x : 0;
}
// Function to precompute the perfect
// squares upto 100000.
static void compute()
{
for (int i = 1; i <= 100000; ++i)
{
pref[i] = pref[i - 1]
+ isPerfectSquare(i);
}
}
// Function to print the sum for each query
static void printSum(int L, int R)
{
int sum = pref[R] - pref[L - 1];
Console.Write(sum+ " ");
}
// Driver code
public static void Main(String[] args)
{
// To calculate the precompute function
compute();
int Q = 4;
int [,]arr = { { 1, 10 },
{ 1, 100 },
{ 2, 25 },
{ 4, 50 } };
// Calling the printSum function
// for every query
for (int i = 0; i < Q; i++)
{
printSum(arr[i, 0], arr[i, 1]);
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find the sum of all
// perfect squares in the given range
// Array to precompute the sum of squares
// from 1 to 100010 so that for every
// query, the answer can be returned in O(1).
var pref= Array(100010).fill(0);
// Function to check if a number is
// a perfect square or not
function isPerfectSquare(x)
{
// Find floating point value of
// square root of x.
var sr = Math.sqrt(x);
// If square root is an integer
return ((sr - Math.floor(sr)) == 0) ? x : 0;
}
// Function to precompute the perfect
// squares upto 100000.
function compute()
{
for (var i = 1; i <= 100000; ++i) {
pref[i] = pref[i - 1]
+ isPerfectSquare(i);
}
}
// Function to print the sum for each query
function printSum(L, R)
{
var sum = pref[R] - pref[L - 1];
document.write(sum + " ");
}
// Driver code
// To calculate the precompute function
compute();
var Q = 4;
arr = [ [ 1, 10 ],
[ 1, 100 ],
[ 2, 25 ],
[ 4, 50 ] ];
// Calling the printSum function
// for every query
for(var i = 0; i < Q; i++)
printSum(arr[i][0], arr[i][1]);
</script>
Producción:
14 385 54 139
Complejidad temporal: O(Q + 10000 * x)
Espacio Auxiliar: O(100010)