Encuentre un subarreglo de tamaño K cuya suma sea un cuadrado perfecto

Posted on by Rudeus Greyrat

Dado un arreglo arr[] y un entero K , la tarea es encontrar un subarreglo de longitud K que tenga una suma que sea un cuadrado perfecto . Si no existe tal subarreglo, imprima -1 . De lo contrario, imprima el subarreglo.

Nota: Puede haber más de un subarreglo posible. Imprime cualquiera de ellos.
Ejemplos:

Entrada: arr[] = {20, 34, 51, 10, 99, 87, 23, 45}, K = 3 
Salida: {10, 99, 87} 
Explicación: La suma de los elementos del subarreglo {10, 99 , 87} es 196, que es un cuadrado perfecto (16 2 = 196).

Entrada: arr[] = {20, 34, 51, 10, 99, 87, 23, 45}, K = 4 
Salida: -1 
Explicación: Ninguno de los subarreglos de tamaño K tiene una suma que sea un cuadrado perfecto.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles de tamaño K y verificar si la suma de cualquier subarreglo generado es un cuadrado perfecto o no. Si se encuentra que es cierto, imprima ese subarreglo. Si ningún subarreglo satisface la condición, imprima «-1» . 
Complejidad temporal: O(N*K) 
Espacio auxiliar: O(K)

Enfoque eficiente: un enfoque eficiente es usar una técnica de ventana deslizante para encontrar la suma de un subarreglo contiguo de tamaño K y luego verificar si la suma es un cuadrado perfecto o no usando la búsqueda binaria . A continuación se detallan los pasos para solucionar este problema:

  1. Calcule la suma de los primeros elementos de la array K y guárdela en una variable, digamos curr_sum .
  2. Luego itere sobre los elementos restantes de la array uno por uno y actualice curr_sum agregando i- ésimo elemento y eliminando (i – K) -ésimo elemento de la array.
  3. Para cada valor de curr_sum obtenido, compruebe si es un número cuadrado perfecto o no.
  4. Si se encuentra que es cierto para cualquier valor de curr_sum , imprima el subarreglo correspondiente.
  5. De lo contrario, imprima -1.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a given number
// is a perfect square or not
bool isPerfectSquare(int n)
{
    // Find square root of n
    double sr = sqrt(n);
 
    // Check if the square root
    // is an integer or not
    return ((sr - floor(sr)) == 0);
}
 
// Function to print the subarray
// whose sum is a perfect square
void SubarrayHavingPerfectSquare(
    vector<int> arr, int k)
{
    pair<int, int> ans;
    int sum = 0, i;
 
    // Sum of first K elements
    for (i = 0; i < k; i++) {
        sum += arr[i];
    }
 
    bool found = false;
 
    // If the first k elements have
    // a sum as perfect square
    if (isPerfectSquare(sum)) {
        ans.first = 0;
        ans.second = i - 1;
    }
    else {
 
        // Iterate through the array
        for (int j = i;
             j < arr.size(); j++) {
 
            sum = sum + arr[j] - arr[j - k];
 
            // If sum is perfect square
            if (isPerfectSquare(sum)) {
                found = true;
                ans.first = j - k + 1;
                ans.second = j;
            }
        }
 
        for (int k = ans.first;
             k <= ans.second; k++) {
            cout << arr[k] << " ";
        }
    }
 
    // If subarray not found
    if (found == false) {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
    // Given array
    vector<int> arr;
 
    arr = { 20, 34, 51, 10,
            99, 87, 23, 45 };
 
    // Given subarray size K
    int K = 3;
 
    // Function Call
    SubarrayHavingPerfectSquare(arr, K);
 
    return 0;
}

Java

// Java program for
// the above approach
class GFG{
     
static class pair
{
  int first, second;
}
// Function to check if a given number
// is a perfect square or not
static boolean isPerfectSquare(int n)
{
  // Find square root of n
  double sr = Math.sqrt(n);
 
  // Check if the square root
  // is an integer or not
  return ((sr - Math.floor(sr)) == 0);
}
 
// Function to print the subarray
// whose sum is a perfect square
static void SubarrayHavingPerfectSquare(int[] arr,
                                        int k)
{
  pair ans = new pair();
  int sum = 0, i;
 
  // Sum of first K elements
  for (i = 0; i < k; i++)
  {
    sum += arr[i];
  }
 
  boolean found = false;
 
  // If the first k elements have
  // a sum as perfect square
  if (isPerfectSquare(sum))
  {
    ans.first = 0;
    ans.second = i - 1;
  }
  else
  {
    // Iterate through the array
    for (int j = i; j < arr.length; j++)
    {
      sum = sum + arr[j] - arr[j - k];
 
      // If sum is perfect square
      if (isPerfectSquare(sum))
      {
        found = true;
        ans.first = j - k + 1;
        ans.second = j;
      }
    }
 
    for (int k1 = ans.first;
             k1 <= ans.second; k1++)
    {
      System.out.print(arr[k1] + " ");
    }
  }
 
  // If subarray not found
  if (found == false)
  {
    System.out.print("-1");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array
  int []arr = {20, 34, 51, 10,
               99, 87, 23, 45};
 
  // Given subarray size K
  int K = 3;
 
  // Function Call
  SubarrayHavingPerfectSquare(arr, K);
 
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program for the above approach
from math import sqrt, ceil, floor
 
# Function to check if a given number
# is a perfect square or not
def isPerfectSquare(n):
 
    # Find square root of n
    sr = sqrt(n)
 
    # Check if the square root
    # is an integer or not
    return ((sr - floor(sr)) == 0)
 
# Function to print the subarray
# whose sum is a perfect square
def SubarrayHavingPerfectSquare(arr, k):
 
    ans = [ 0, 0 ]
    sum = 0
 
    # Sum of first K elements
    i = 0
    while i < k:
        sum += arr[i]
        i += 1
 
    found = False
 
    # If the first k elements have
    # a sum as perfect square
    if (isPerfectSquare(sum)):
        ans[0] = 0
        ans[1] = i - 1
 
    else:
 
        # Iterate through the array
        for j in range(i, len(arr)):
            sum = sum + arr[j] - arr[j - k]
 
            # If sum is perfect square
            if (isPerfectSquare(sum)):
                found = True
                ans[0] = j - k + 1
                ans[1] = j
 
        for k in range(ans[0], ans[1] + 1):
            print(arr[k], end = " ")
 
    # If subarray not found
    if (found == False):
        print("-1")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [ 20, 34, 51, 10,
            99, 87, 23, 45 ]
 
    # Given subarray size K
    K = 3
 
    # Function call
    SubarrayHavingPerfectSquare(arr, K)
 
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
class GFG{
     
class pair
{
  public int first, second;
}
   
// Function to check if a given number
// is a perfect square or not
static bool isPerfectSquare(int n)
{
  // Find square root of n
  double sr = Math.Sqrt(n);
 
  // Check if the square root
  // is an integer or not
  return ((sr - Math.Floor(sr)) == 0);
}
 
// Function to print the subarray
// whose sum is a perfect square
static void SubarrayHavingPerfectSquare(int[] arr,
                                        int k)
{
  pair ans = new pair();
  int sum = 0, i;
 
  // Sum of first K elements
  for (i = 0; i < k; i++)
  {
    sum += arr[i];
  }
 
  bool found = false;
 
  // If the first k elements have
  // a sum as perfect square
  if (isPerfectSquare(sum))
  {
    ans.first = 0;
    ans.second = i - 1;
  }
  else
  {
    // Iterate through the array
    for (int j = i; j < arr.Length; j++)
    {
      sum = sum + arr[j] - arr[j - k];
 
      // If sum is perfect square
      if (isPerfectSquare(sum))
      {
        found = true;
        ans.first = j - k + 1;
        ans.second = j;
      }
    }
 
    for (int k1 = ans.first;
             k1 <= ans.second; k1++)
    {
      Console.Write(arr[k1] + " ");
    }
  }
 
  // If subarray not found
  if (found == false)
  {
    Console.Write("-1");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array
  int []arr = {20, 34, 51, 10,
               99, 87, 23, 45};
 
  // Given subarray size K
  int K = 3;
 
  // Function Call
  SubarrayHavingPerfectSquare(arr, K);
 
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to check if a given number
// is a perfect square or not
function isPerfectSquare(n)
{
    // Find square root of n
    var sr = Math.sqrt(n);
 
    // Check if the square root
    // is an integer or not
    return ((sr - Math.floor(sr)) == 0);
}
 
// Function to print the subarray
// whose sum is a perfect square
function SubarrayHavingPerfectSquare( arr, k)
{
    var ans = [];
    var sum = 0, i;
 
    // Sum of first K elements
    for (i = 0; i < k; i++) {
        sum += arr[i];
    }
 
    var found = false;
 
    // If the first k elements have
    // a sum as perfect square
    if (isPerfectSquare(sum)) {
        ans[0] = 0;
        ans[1] = i - 1;
    }
    else {
 
        // Iterate through the array
        for (var j = i;
             j < arr.length; j++) {
 
            sum = sum + arr[j] - arr[j - k];
 
            // If sum is perfect square
            if (isPerfectSquare(sum)) {
                found = true;
                ans[0] = j - k + 1;
                ans[1] = j;
            }
        }
 
        for (var k = ans[0];
             k <= ans[1]; k++) {
            document.write( arr[k] + " ");
        }
    }
 
    // If subarray not found
    if (found == false) {
        document.write( "-1");
    }
}
 
// Driver Code
// Given array
var arr = [20, 34, 51, 10,
        99, 87, 23, 45 ];
// Given subarray size K
var K = 3;
// Function Call
SubarrayHavingPerfectSquare(arr, K);
 
 
</script>
Producción: 

10 99 87

Complejidad de tiempo: O(N*log(suma)) 
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 *