Comprobar si la suma de un subarreglo dentro de un rango dado es un cuadrado perfecto o no

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N y una array range[] , la tarea es comprobar si la suma de la subarreglo {range[0], .. , range[1]} es un cuadrado perfecto o no. Si la suma es un cuadrado perfecto, imprima la raíz cuadrada de la suma. De lo contrario, imprima -1.

Ejemplo :

Entrada: arr[] = {2, 19, 33, 48, 90, 100}, rango = [1, 3] 
Salida: 10 
Explicación: 
La suma del elemento desde la posición 1 hasta la posición 3 es 19 + 33 + 48 = 100 , que es un cuadrado perfecto de 10.

Entrada: arr[] = {13, 15, 30, 55, 87}, rango = [0, 1] 
Salida: -1

Enfoque ingenuo: el enfoque más simple es iterar sobre el subarreglo y verificar si la suma del subarreglo es un cuadrado perfecto o no.

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la búsqueda binaria para calcular la raíz cuadrada de la suma del subarreglo. Siga los pasos a continuación:

  1. Calcule la suma del subarreglo en el rango dado[] .
  2. Ahora, use la búsqueda binaria para encontrar la raíz cuadrada de la suma en el rango de 0 a suma.
  3. Encuentre el elemento medio desde el inicio y el último valor y compare el valor de medio 2 con la suma .
  4. Si el valor de mid 2 es igual a la suma, se encuentra un cuadrado perfecto, luego devuelve mid.
  5. Si el valor de mid 2 es mayor que la suma, entonces la respuesta solo puede estar en el lado derecho del rango después del elemento mid. Entonces recurra a la derecha y reduzca el espacio de búsqueda a 0 a mid – 1 .
  6. Si el valor de mid 2 es menor que sum , reduzca el espacio de búsqueda a mid + 1 para sum.

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

C++

// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the square
// root of the sum of a subarray in
// a given range
int checkForPerfectSquare(vector<int> arr,
                          int i, int j)
{
    int mid, sum = 0;
 
    // Calculate the sum of array
    // elements within a given range
    for (int m = i; m <= j; m++) {
        sum += arr[m];
    }
 
    // Finding the square root
    int low = 0, high = sum / 2;
    while (low <= high) {
        mid = low + (high - low) / 2;
 
        // If a perfect square is found
        if (mid * mid == sum) {
            return mid;
        }
 
        // Reduce the search space if
        // the value is greater than sum
        else if (mid * mid > sum) {
            high = mid - 1;
        }
 
        // Reduce the search space if
        // the value if smaller than sum
        else {
            low = mid + 1;
        }
    }
    return -1;
}
 
// Driver Code
int main()
{
    // Given Array
    vector<int> arr;
    arr = { 2, 19, 33, 48, 90, 100 };
 
    // Given range
    int L = 1, R = 3;
 
    // Function Call
    cout << checkForPerfectSquare(arr, L, R);
    return 0;
}

Java

// Java implementation of
// the above approach
import java.util.*;
class GFG{
 
// Function to calculate the square
// root of the sum of a subarray in
// a given range
static int checkForPerfectSquare(int []arr,
                                 int i, int j)
{
  int mid, sum = 0;
 
  // Calculate the sum of array
  // elements within a given range
  for (int m = i; m <= j; m++)
  {
    sum += arr[m];
  }
 
  // Finding the square root
  int low = 0, high = sum / 2;
  while (low <= high)
  {
    mid = low + (high - low) / 2;
 
    // If a perfect square
    // is found
    if (mid * mid == sum)
    {
      return mid;
    }
 
    // Reduce the search space
    // if the value is greater
    // than sum
    else if (mid * mid > sum)
    {
      high = mid - 1;
    }
 
    // Reduce the search space
    // if the value if smaller
    // than sum
    else
    {
      low = mid + 1;
    }
  }
  return -1;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given Array
  int []arr = {2, 19, 33,
               48, 90, 100};
 
  // Given range
  int L = 1, R = 3;
 
  // Function Call
  System.out.print(
         checkForPerfectSquare(arr, L, R));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of
# the above approach
 
# Function to calculate the square
# root of the sum of a subarray in
# a given range
def checkForPerfectSquare(arr, i, j):
 
    mid, sum = 0, 0
 
    # Calculate the sum of array
    # elements within a given range
    for m in range(i, j + 1):
        sum += arr[m]
 
    # Finding the square root
    low = 0
    high = sum // 2
     
    while (low <= high):
        mid = low + (high - low) // 2
 
        # If a perfect square is found
        if (mid * mid == sum):
            return mid
 
        # Reduce the search space if
        # the value is greater than sum
        elif (mid * mid > sum):
            high = mid - 1
 
        # Reduce the search space if
        # the value if smaller than sum
        else:
            low = mid + 1
 
    return -1
 
# Driver Code
if __name__ == '__main__':
 
    # Given Array
    arr = [ 2, 19, 33, 48, 90, 100 ]
 
    # Given range
    L = 1
    R = 3
 
    # Function call
    print(checkForPerfectSquare(arr, L, R))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of
// the above approach
using System;
class GFG{
 
// Function to calculate the square
// root of the sum of a subarray in
// a given range
static int checkForPerfectSquare(int []arr,
                                 int i, int j)
{
  int mid, sum = 0;
 
  // Calculate the sum of array
  // elements within a given range
  for (int m = i; m <= j; m++)
  {
    sum += arr[m];
  }
 
  // Finding the square root
  int low = 0, high = sum / 2;
  while (low <= high)
  {
    mid = low + (high - low) / 2;
 
    // If a perfect square
    // is found
    if (mid * mid == sum)
    {
      return mid;
    }
 
    // Reduce the search space
    // if the value is greater
    // than sum
    else if (mid * mid > sum)
    {
      high = mid - 1;
    }
 
    // Reduce the search space
    // if the value if smaller
    // than sum
    else
    {
      low = mid + 1;
    }
  }
  return -1;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given Array
  int []arr = {2, 19, 33,
               48, 90, 100};
 
  // Given range
  int L = 1, R = 3;
 
  // Function Call
  Console.Write(checkForPerfectSquare(arr,
                                      L, R));}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of
// the above approach
 
// Function to calculate the square
// root of the sum of a subarray in
// a given range
function checkForPerfectSquare(arr, i, j)
{
    let mid, sum = 0;
 
    // Calculate the sum of array
    // elements within a given range
    for(let m = i; m <= j; m++)
    {
        sum += arr[m];
    }
 
    // Finding the square root
    let low = 0, high = parseInt(sum / 2);
     
    while (low <= high)
    {
        mid = low + parseInt((high - low) / 2);
 
        // If a perfect square is found
        if (mid * mid == sum)
        {
            return mid;
        }
 
        // Reduce the search space if
        // the value is greater than sum
        else if (mid * mid > sum)
        {
            high = mid - 1;
        }
 
        // Reduce the search space if
        // the value if smaller than sum
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}
 
// Driver Code
 
// Given Array
let arr = [ 2, 19, 33, 48, 90, 100 ];
 
// Given range
let L = 1, R = 3;
 
// Function Call
document.write(checkForPerfectSquare(arr, L, R));
 
// This code is contributed by rishavmahato348
 
</script>
Producción: 

10

Complejidad de tiempo: O(max(log(sum), N)) 
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por shawavisek35 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 *