Encuentre la suma de todos los cuadrados perfectos impares en el rango [L, R]

Posted on by Rudeus Greyrat

Dados dos enteros L y R . La tarea es encontrar la suma de todos los números impares que son cuadrados perfectos en el rango [L, R] .

Ejemplos :

Entrada : L = 1, R = 9
Salida : 10
Explicación : Los números impares en el rango son 1, 3, 5, 7, 9 y solo 1, 9 son cuadrados perfectos de 1, 3. Entonces, 1 + 9 = 10 .

Entrada : L = 50, R = 10 000
Salida : 166566

 

Enfoque ingenuo : la idea básica para resolver este problema es atravesar los números en el rango L a R, y para cada número impar, verificar si también es un cuadrado perfecto. 

Tiempo Complejidad: O(RL) 
Espacio Auxiliar: O(1) 

Enfoque Eficiente : El enfoque de la solución se basa en el concepto matemático de secuencia. La idea es usar la suma del cuadrado de los primeros N números impares. 

Cuadrados de los primeros n números naturales impares = \sum (2n-1)^{2} = \frac{n(2n+1)(2n-1)}{3}

Siga los pasos a continuación para resolver el problema:

  1. Comprueba el número de cuadrados perfectos entre 1 y el número impar cuadrado perfecto justo mayor o igual que L.
  2. Verifique el conteo de cuadrados perfectos impares en el rango [1, L) .
  3. Calcule la suma (sum1)  de cuadrados perfectos impares en el rango [1, L) .
  4. Verifique el conteo de cuadrados perfectos en el rango [1, R] .
  5. Verifique el conteo de cuadrados perfectos impares en el rango [1, R] .
  6. Calcule la suma (sum2) de cuadrados perfectos impares en el rango [1, R] .
  7. Resta sum1 de sum2 para obtener la suma de números impares que son cuadrados perfectos en el rango [L, R].

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation for the above approach
#include <cmath>
#include <iostream>
using namespace std;
 
// Function to find sum of all the odd
// numbers,which are perfect squares
// in range [L, R]
int findSum(int L, int R)
{
    // If L > R or both less than 0
    if (L < 0 || R < 0 || L > R)
        return -1;
 
    int l, r, n1, n2, s1, s2;
 
    // Check count of numbers
    // which are perfect squares between 
    // 1 & perfect squared odd number
    // just greater or equal to L
    l = ceil(sqrt(L));
    if (!(l & 1))
        l++;
 
    // Check count of numbers which
    // are perfect squares in range [1, R]
    r = floor(sqrt(R));
    if (!(r & 1))
        r--;
 
    // Check count of odd numbers which
    // are perfect squares in range [1, L)
    n1 = floor((float)l / 2);
 
    // Check count of odd numbers which
    // are perfect squares in range [1, R]
    n2 = ceil((float)r / 2);
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, L)
    s1 = n1 * ((4 * n1 * n1) - 1) / 3;
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, R]
    s2 = n2 * ((4 * n2 * n2) - 1) / 3;
 
    // Return sum of odd numbers which
    // are perfect squares in range [L, R]
    return s2 - s1;
}
 
// Driver Code
int main()
{
    int L = 1;
    int R = 9;
 
    cout << findSum(L, R);
    return 0;
}

Java

// Java implementation for the above approach
import java.util.*;
public class GFG
{
// Function to find sum of all the odd
// numbers,which are perfect squares
// in range [L, R]
static int findSum(int L, int R)
{
    // If L > R or both less than 0
    if (L < 0 || R < 0 || L > R)
        return -1;
 
    int l, r, n1, n2, s1, s2;
 
    // Check count of numbers
    // which are perfect squares between 
    // 1 & perfect squared odd number
    // just greater or equal to L
    l = (int)Math.ceil(Math.sqrt(L));
    if ((l & 1) == 0)
        l++;
 
    // Check count of numbers which
    // are perfect squares in range [1, R]
    r = (int)Math.floor(Math.sqrt(R));
    if ((r & 1) == 0)
        r--;
 
    // Check count of odd numbers which
    // are perfect squares in range [1, L)
    n1 = (int)Math.floor((float)l / 2);
 
    // Check count of odd numbers which
    // are perfect squares in range [1, R]
    n2 = (int)Math.ceil((float)r / 2);
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, L)
    s1 = n1 * ((4 * n1 * n1) - 1) / 3;
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, R]
    s2 = n2 * ((4 * n2 * n2) - 1) / 3;
 
    // Return sum of odd numbers which
    // are perfect squares in range [L, R]
    return s2 - s1;
}
 
// Driver Code
public static void main(String args[])
{
    int L = 1;
    int R = 9;
 
    System.out.println(findSum(L, R));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python3 implementation for the above approach
import math
 
# Function to find sum of all the odd
# numbers,which are perfect squares
# in range [L, R]
def findSum(L, R):
     
    # If L > R or both less than 0
    if (L < 0 or R < 0 or L > R):
        return -1
         
    # Check count of numbers which are
    # perfect squares between 1 & perfect
    # squared odd number just greater or
    # equal to L
    l = math.ceil(math.sqrt(L))
    if (not (l & 1)):
        l += 1
 
    # Check count of numbers which
    # are perfect squares in range [1, R]
    r = math.floor(math.sqrt(R))
    if (not (r & 1)):
        r -= 1
 
    # Check count of odd numbers which
    # are perfect squares in range [1, L)
    n1 = math.floor(l / 2)
 
    # Check count of odd numbers which
    # are perfect squares in range [1, R]
    n2 = math.ceil(r / 2)
 
    # Calculate sum of odd numbers which
    # are perfect squares in range [1, L)
    s1 = int(n1 * ((4 * n1 * n1) - 1) / 3)
 
    # Calculate sum of odd numbers which
    # are perfect squares in range [1, R]
    s2 = int(n2 * ((4 * n2 * n2) - 1) / 3)
 
    # Return sum of odd numbers which
    # are perfect squares in range [L, R]
    return s2 - s1
 
# Driver Code
if __name__ == "__main__":
 
    L = 1
    R = 9
 
    print(findSum(L, R))
 
# This code is contributed by rakeshsahni

C#

// C# implementation for the above approach
using System;
class GFG
{
   
// Function to find sum of all the odd
// numbers,which are perfect squares
// in range [L, R]
static int findSum(int L, int R)
{
   
    // If L > R or both less than 0
    if (L < 0 || R < 0 || L > R)
        return -1;
 
    int l, r, n1, n2, s1, s2;
 
    // Check count of numbers
    // which are perfect squares between 
    // 1 & perfect squared odd number
    // just greater or equal to L
    l = (int)Math.Ceiling(Math.Sqrt(L));
    if ((l & 1) == 0)
        l++;
 
    // Check count of numbers which
    // are perfect squares in range [1, R]
    r = (int)Math.Floor(Math.Sqrt(R));
    if ((r & 1) == 0)
        r--;
 
    // Check count of odd numbers which
    // are perfect squares in range [1, L)
    n1 = (int)Math.Floor((float)l / 2);
 
    // Check count of odd numbers which
    // are perfect squares in range [1, R]
    n2 = (int)Math.Ceiling((float)r / 2);
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, L)
    s1 = n1 * ((4 * n1 * n1) - 1) / 3;
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, R]
    s2 = n2 * ((4 * n2 * n2) - 1) / 3;
 
    // Return sum of odd numbers which
    // are perfect squares in range [L, R]
    return s2 - s1;
}
 
// Driver Code
public static void Main()
{
    int L = 1;
    int R = 9;
 
    Console.Write(findSum(L, R));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
// JavaScript implementation for the above approach
 
// Function to find sum of all the odd
// numbers,which are perfect squares
// in range [L, R]
function findSum(L, R)
{
     
    // If L > R or both less than 0
    if (L < 0 || R < 0 || L > R)
        return -1;
 
    let l, r, n1, n2, s1, s2;
 
    // Check count of numbers
    // which are perfect squares between 
    // 1 & perfect squared odd number
    // just greater or equal to L
    l = Math.ceil(Math.sqrt(L));
    if (!(l & 1))
        l++;
 
    // Check count of numbers which
    // are perfect squares in range [1, R]
    r = Math.floor(Math.sqrt(R));
    if (!(r & 1))
        r--;
 
    // Check count of odd numbers which
    // are perfect squares in range [1, L)
    n1 = Math.floor(l / 2);
 
    // Check count of odd numbers which
    // are perfect squares in range [1, R]
    n2 = Math.ceil(r / 2);
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, L)
    s1 = n1 * ((4 * n1 * n1) - 1) / 3;
 
    // Calculate sum of odd numbers which
    // are perfect squares in range [1, R]
    s2 = n2 * ((4 * n2 * n2) - 1) / 3;
 
    // Return sum of odd numbers which
    // are perfect squares in range [L, R]
    return s2 - s1;
}
 
// Driver Code
let L = 1;
let R = 9;
 
document.write(findSum(L, R));
 
// This code is contributed by Potta Lokesh
 
</script>
Producción

10

Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *