Subarreglos cuya suma es un cuadrado perfecto

Dada una array , arr[] de tamaño N , la tarea es imprimir los índices inicial y final de todas las subarreglas cuya suma es un cuadrado perfecto .

Ejemplos :

Entrada: arr[] = {65, 79, 81}
Salida: (0, 1) (0, 2) (2, 2)
Explicación: 
suma de subarreglo cuyo índice inicial y final es (0, 1) = 65 + 79 = 144 = 12 ² 
Suma de subarreglo cuyo índice inicial y final es (0, 2} = 65 + 79 + 81 = 225 = 15 ² 
Suma de subarreglo cuyo índice inicial y final es {2, 2} = 81 = 9 ²

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: (0, 0) (1, 3) (3, 3) (3, 4) 

Enfoque: El problema se puede resolver utilizando la técnica Prefix Sum Array . La idea es encontrar la suma de todos los subarreglos usando Prefix Sum Array . Para cada subarreglo, verifique si la suma del subarreglo es un cuadrado perfecto o no. Si se encuentra que es cierto para cualquier subarreglo, imprima los índices inicial y final de ese subarreglo. Siga los pasos a continuación para resolver el problema.

1. Inicialice una variable, diga currSubSum para almacenar la suma actual del subarreglo.
2. Iterar sobre el arreglo para generar todos los subarreglos posibles del arreglo dado .
3. Calcule la suma de cada subarreglo y para cada suma de subarreglo, verifique si es un cuadrado perfecto o no.
4. Si se encuentra que es cierto para cualquier subarreglo, imprima los índices inicial y final del subarreglo.

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the start and end
// indices of all subarrays whose sum
// is a perfect square
void PrintIndexes(int arr[], int N)
{
 
    for (int i = 0; i < N; i++) {
 
        // Stores the current
        // subarray sum
        int currSubSum = 0;
 
        for (int j = i; j < N; j++) {
 
            // Update current subarray sum
            currSubSum += arr[j];
 
            // Stores the square root
            // of currSubSum
            int sq = sqrt(currSubSum);
 
            // Check if currSubSum is
            // a perfect square or not
            if (sq * sq == currSubSum) {
                cout << "(" << i << ", "
                     << j << ") ";
            }
        }
    }
}
 
// Driver Code
int main()
{
 
    int arr[] = { 65, 79, 81 };
    int N = sizeof(arr) / sizeof(arr[0]);
    PrintIndexes(arr, N);
}

// Java program to implement
// the above approach
import java.io.*;
 
class GFG{
     
// Function to print the start and end
// indices of all subarrays whose sum
// is a perfect square
static void PrintIndexes(int arr[], int N)
{
    for(int i = 0; i < N; i++)
    {
         
        // Stores the current
        // subarray sum
        int currSubSum = 0;
   
        for(int j = i; j < N; j++)
        {
             
            // Update current subarray sum
            currSubSum += arr[j];
   
            // Stores the square root
            // of currSubSum
            int sq = (int)Math.sqrt(currSubSum);
   
            // Check if currSubSum is
            // a perfect square or not
            if (sq * sq == currSubSum)
            {
                System.out.print("(" + i + "," +
                                 j + ")" + " ");
            }
        }
    }
}
 
// Driver code
public static void main (String[] args)
throws java.lang.Exception
{
    int arr[] = { 65, 79, 81 };
     
    PrintIndexes(arr, arr.length);
}
}
 
// This code is contributed by bikram2001jha

# Python3 program to implement
# the above approach
import math
 
# Function to print the start and end
# indices of all subarrays whose sum
# is a perfect square
def PrintIndexes(arr, N):
  
    for i in range(N):
  
        # Stores the current
        # subarray sum
        currSubSum = 0
  
        for j in range(i, N, 1):
             
            # Update current subarray sum
            currSubSum += arr[j]
  
            # Stores the square root
            # of currSubSum
            sq = int(math.sqrt(currSubSum))
  
            # Check if currSubSum is
            # a perfect square or not
            if (sq * sq == currSubSum):
                print("(", i, ",",
                           j, ")", end = " ")
                            
# Driver Code
arr = [ 65, 79, 81 ]
N = len(arr)
 
PrintIndexes(arr, N)
 
# This code is contributed by sanjoy_62

// C# program to implement
// the above approach
using System;
class GFG{
     
// Function to print the start
// and end indices of all
// subarrays whose sum
// is a perfect square
static void PrintIndexes(int []arr,
                         int N)
{
  for(int i = 0; i < N; i++)
  {
    // Stores the current
    // subarray sum
    int currSubSum = 0;
 
    for(int j = i; j < N; j++)
    {
      // Update current subarray sum
      currSubSum += arr[j];
 
      // Stores the square root
      // of currSubSum
      int sq = (int)Math.Sqrt(currSubSum);
 
      // Check if currSubSum is
      // a perfect square or not
      if (sq * sq == currSubSum)
      {
        Console.Write("(" + i + "," +
                      j + ")" + " ");
      }
    }
  }
}
 
// Driver code
public static void Main(String[] args)
{
  int []arr = {65, 79, 81};
  PrintIndexes(arr, arr.Length);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program to implement
// the above approach
 
// Function to print the start and end
// indices of all subarrays whose sum
// is a perfect square
function PrintIndexes(arr, N)
{
    for(let i = 0; i < N; i++)
    {
         
        // Stores the current
        // subarray sum
        let currSubSum = 0;
   
        for(let j = i; j < N; j++)
        {
             
            // Update current subarray sum
            currSubSum += arr[j];
   
            // Stores the square root
            // of currSubSum
            let sq = Math.floor(Math.sqrt(currSubSum));
   
            // Check if currSubSum is
            // a perfect square or not
            if (sq * sq == currSubSum)
            {
                document.write("(" + i + "," +
                                 j + ")" + " ");
            }
        }
    }
}
 
// Driver Code
 
        let arr = [ 65, 79, 81 ];
     
    PrintIndexes(arr, arr.length);
 
</script>

(0, 1) (0, 2) (2, 2)

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