Conteo de pares en una array cuya suma es un cuadrado perfecto

Dada una array  de elementos distintos, la tarea es encontrar el número total de dos pares de elementos de la array cuya suma es un cuadrado perfecto . Ejemplos:

Entrada: arr[] = {2, 3, 6, 9, 10, 20} Salida: 2 Solo los pares posibles son (3, 6) y (6, 10) Entrada: arr[] = {9, 2, 5, 1} Salida: 0

Enfoque ingenuo: use bucles anidados y verifique cada par posible para ver si su suma es un cuadrado perfecto o no. Esta técnica no es efectiva cuando la longitud de la array es muy grande. Enfoque eficiente:

• Almacene todos los elementos de la array en un HashSet llamado nums y guarde la suma de los dos elementos máximos en una variable llamada max .
• Está claro que la suma de dos elementos cualquiera de la array no excederá max . Entonces, encuentra todos los cuadrados perfectos que son ≤ max y guárdalos en una ArrayList llamada perfectSquares .
• Ahora, para cada elemento de la array, diga arr[i] y para cada cuadrado perfecto guardado en perfectSquares , verifique si perfectSquares.get(i) – arr[i] existe en nums o no, es decir, si hay algún elemento en la array original que cuando se agrega con el elemento elegido actualmente da cualquier cuadrado perfecto de la lista.
• Si se cumple la condición anterior, incremente la variable de conteo .
• Imprime el valor de conteo al final.

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

// CPP implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
 
// Function to return an ArrayList containing
// all the perfect squares upto n
vector<int> getPerfectSquares(int n)
{
    vector<int> perfectSquares;
    int current = 1, i = 1;
 
    // while current perfect square is less than or equal to n
    while (current <= n)
    {
        perfectSquares.push_back(current);
        current = static_cast<int>(pow(++i, 2));
    }
    return perfectSquares;
}
 
// Function to print the sum of maximum
// two elements from the array
int maxPairSum(vector<int> &arr)
{
    int n = arr.size();
    int max, secondMax;
    if (arr[0] > arr[1])
    {
        max = arr[0];
        secondMax = arr[1];
    }
    else
    {
        max = arr[1];
        secondMax = arr[0];
    }
 
    for (int i = 2; i < n; i++)
    {
        if (arr[i] > max)
        {
            secondMax = max;
            max = arr[i];
        }
        else if (arr[i] > secondMax)
        {
            secondMax = arr[i];
        }
    }
    return (max + secondMax);
}
 
// Function to return the count of numbers that
// when added with n give a perfect square
int countPairsWith(int n, vector<int> &perfectSquares, unordered_set<int> &nums)
{
    int count = 0;
    for (int i = 0; i < perfectSquares.size(); i++)
    {
        int temp = perfectSquares[i] - n;
 
        // temp > n is checked so that pairs
        // (x, y) and (y, x) don't get counted twice
        if (temp > n && find(nums.begin(), nums.end(), temp) != nums.end())
        {
            count++;
        }
    }
    return count;
}
 
// Function to count the pairs whose sum is a perfect square
int countPairs(vector<int> &arr)
{
    int i, n = arr.size();
 
    // Sum of the maximum two elements from the array
    int max = maxPairSum(arr);
 
    // List of perfect squares upto max
    vector<int> perfectSquares = getPerfectSquares(max);
 
    // Contains all the array elements
    unordered_set<int> nums;
    for (i = 0; i < n; i++)
    {
        nums.insert(arr[i]);
    }
 
    int count = 0;
    for (i = 0; i < n; i++)
    {
 
        // Add count of the elements that when
        // added with arr[i] give a perfect square
        count += countPairsWith(arr[i], perfectSquares, nums);
    }
    return count;
}
 
// Driver code
int main()
{
    vector<int> arr = {2, 3, 6, 9, 10, 20};
 
    cout << countPairs(arr) << endl;
    return 0;
}
// This code is contributed by mits

// Java implementation of the approach
import java.util.*;
 
public class GFG {
 
    // Function to return an ArrayList containing
    // all the perfect squares upto n
    public static ArrayList<Integer> getPerfectSquares(int n)
    {
        ArrayList<Integer> perfectSquares = new ArrayList<>();
        int current = 1, i = 1;
 
        // while current perfect square is less than or equal to n
        while (current <= n) {
            perfectSquares.add(current);
            current = (int)Math.pow(++i, 2);
        }
        return perfectSquares;
    }
 
    // Function to print the sum of maximum
    // two elements from the array
    public static int maxPairSum(int arr[])
    {
        int n = arr.length;
        int max, secondMax;
        if (arr[0] > arr[1]) {
            max = arr[0];
            secondMax = arr[1];
        }
        else {
            max = arr[1];
            secondMax = arr[0];
        }
 
        for (int i = 2; i < n; i++) {
            if (arr[i] > max) {
                secondMax = max;
                max = arr[i];
            }
            else if (arr[i] > secondMax) {
                secondMax = arr[i];
            }
        }
        return (max + secondMax);
    }
 
    // Function to return the count of numbers that
    // when added with n give a perfect square
    public static int countPairsWith(
        int n, ArrayList<Integer> perfectSquares,
                            HashSet<Integer> nums)
    {
        int count = 0;
        for (int i = 0; i < perfectSquares.size(); i++) {
            int temp = perfectSquares.get(i) - n;
 
            // temp > n is checked so that pairs
            // (x, y) and (y, x) don't get counted twice
            if (temp > n && nums.contains(temp))
                count++;
        }
        return count;
    }
 
    // Function to count the pairs whose sum is a perfect square
    public static int countPairs(int arr[])
    {
        int i, n = arr.length;
 
        // Sum of the maximum two elements from the array
        int max = maxPairSum(arr);
 
        // List of perfect squares upto max
        ArrayList<Integer> perfectSquares =
                                    getPerfectSquares(max);
 
        // Contains all the array elements
        HashSet<Integer> nums = new HashSet<>();
        for (i = 0; i < n; i++)
            nums.add(arr[i]);
 
        int count = 0;
        for (i = 0; i < n; i++) {
 
            // Add count of the elements that when
            // added with arr[i] give a perfect square
            count += countPairsWith(arr[i], perfectSquares, nums);
        }
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 6, 9, 10, 20 };
 
        System.out.println(countPairs(arr));
    }
}

# Python3 implementation of the approach
 
# Function to return an ArrayList containing
# all the perfect squares upto n
def getPerfectSquares(n):
 
    perfectSquares = [];
    current = 1;
    i = 1;
 
    # while current perfect square is
    # less than or equal to n
    while (current <= n):
        perfectSquares.append(current);
        i += 1;
        current = int(pow(i, 2));
 
    return perfectSquares;
 
# Function to print the sum of maximum
# two elements from the array
def maxPairSum(arr):
 
    n = len(arr);
    max = 0;
    secondMax = 0;
    if (arr[0] > arr[1]):
        max = arr[0];
        secondMax = arr[1];
    else:
        max = arr[1];
        secondMax = arr[0];
 
    for i in range(2, n):
        if (arr[i] > max):
            secondMax = max;
            max = arr[i];
        elif (arr[i] > secondMax):
            secondMax = arr[i];
 
    return (max + secondMax);
 
# Function to return the count of numbers that
# when added with n give a perfect square
def countPairsWith(n, perfectSquares, nums):
 
    count = 0;
    for i in range(len(perfectSquares)):
        temp = perfectSquares[i] - n;
 
        # temp > n is checked so that pairs
        # (x, y) and (y, x) don't get counted twice
        if (temp > n and (temp in nums)):
            count += 1;
 
    return count;
 
# Function to count the pairs whose
# sum is a perfect square
def countPairs(arr):
 
    n = len(arr);
 
    # Sum of the maximum two elements
    # from the array
    max = maxPairSum(arr);
 
    # List of perfect squares upto max
    perfectSquares = getPerfectSquares(max);
 
    # Contains all the array elements
    nums = [];
    for i in range(n):
        nums.append(arr[i]);
 
    count = 0;
    for i in range(n):
 
        # Add count of the elements that when
        # added with arr[i] give a perfect square
        count += countPairsWith(arr[i],
                 perfectSquares, nums);
    return count;
 
# Driver code
arr = [ 2, 3, 6, 9, 10, 20 ];
print(countPairs(arr));
 
# This code is contributed by mits

// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
 
public class GFG {
 
    // Function to return an ArrayList containing
    // all the perfect squares upto n
    public static ArrayList getPerfectSquares(int n)
    {
        ArrayList perfectSquares = new ArrayList();
        int current = 1, i = 1;
 
        // while current perfect square is less than or equal to n
        while (current <= n) {
            perfectSquares.Add(current);
            current = (int)Math.Pow(++i, 2);
        }
        return perfectSquares;
    }
 
    // Function to print the sum of maximum
    // two elements from the array
    public static int maxPairSum(int[] arr)
    {
        int n = arr.Length;
        int max, secondMax;
        if (arr[0] > arr[1]) {
            max = arr[0];
            secondMax = arr[1];
        }
        else {
            max = arr[1];
            secondMax = arr[0];
        }
 
        for (int i = 2; i < n; i++) {
            if (arr[i] > max) {
                secondMax = max;
                max = arr[i];
            }
            else if (arr[i] > secondMax) {
                secondMax = arr[i];
            }
        }
        return (max + secondMax);
    }
 
    // Function to return the count of numbers that
    // when added with n give a perfect square
    public static int countPairsWith(
        int n, ArrayList perfectSquares, ArrayList nums)
    {
        int count = 0;
        for (int i = 0; i < perfectSquares.Count; i++) {
            int temp = (int)perfectSquares[i] - n;
 
            // temp > n is checked so that pairs
            // (x, y) and (y, x) don't get counted twice
            if (temp > n && nums.Contains(temp))
                count++;
        }
        return count;
    }
 
    // Function to count the pairs whose sum is a perfect square
    public static int countPairs(int[] arr)
    {
        int i, n = arr.Length;
 
        // Sum of the maximum two elements from the array
        int max = maxPairSum(arr);
 
        // List of perfect squares upto max
        ArrayList perfectSquares = getPerfectSquares(max);
 
        // Contains all the array elements
        ArrayList nums = new ArrayList();
        for (i = 0; i < n; i++)
            nums.Add(arr[i]);
 
        int count = 0;
        for (i = 0; i < n; i++) {
 
            // Add count of the elements that when
            // added with arr[i] give a perfect square
            count += countPairsWith(arr[i], perfectSquares, nums);
        }
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 2, 3, 6, 9, 10, 20 };
 
        Console.WriteLine(countPairs(arr));
    }
}
// This code is contributed by mits

<?php
// PHP implementation of the approach
 
// Function to return an ArrayList containing
// all the perfect squares upto n
function getPerfectSquares($n)
{
    $perfectSquares = array();
    $current = 1;
    $i = 1;
 
    // while current perfect square
    // is less than or equal to n
    while ($current <= $n)
    {
        array_push($perfectSquares, $current);
        $current = (int)pow(++$i, 2);
    }
    return $perfectSquares;
}
 
// Function to print the sum of maximum
// two elements from the array
function maxPairSum($arr)
{
    $n = count($arr);
    $max;
    $secondMax;
    if ($arr[0] > $arr[1])
    {
        $max = $arr[0];
        $secondMax = $arr[1];
    }
    else
    {
        $max = $arr[1];
        $secondMax = $arr[0];
    }
 
    for ($i = 2; $i < $n; $i++)
    {
        if ($arr[$i] > $max)
        {
            $secondMax = $max;
            $max = $arr[$i];
        }
        else if ($arr[$i] > $secondMax)
        {
            $secondMax = $arr[$i];
        }
    }
    return ($max + $secondMax);
}
 
// Function to return the count of numbers that
// when added with n give a perfect square
function countPairsWith($n, $perfectSquares, $nums)
{
    $count = 0;
    for ($i = 0; $i < count($perfectSquares); $i++)
    {
        $temp = $perfectSquares[$i] - $n;
 
        // temp > n is checked so that pairs
        // (x, y) and (y, x) don't get counted twice
        if ($temp > $n && in_array($temp, $nums))
            $count++;
    }
    return $count;
}
 
// Function to count the pairs whose
// sum is a perfect square
function countPairs($arr)
{
    $n = count($arr);
 
    // Sum of the maximum two elements
    // from the array
    $max = maxPairSum($arr);
 
    // List of perfect squares upto max
    $perfectSquares = getPerfectSquares($max);
 
    // Contains all the array elements
    $nums = array();
    for ($i = 0; $i < $n; $i++)
        array_push($nums, $arr[$i]);
 
    $count = 0;
    for ($i = 0; $i < $n; $i++)
    {
 
        // Add count of the elements that when
        // added with arr[i] give a perfect square
        $count += countPairsWith($arr[$i],
                                 $perfectSquares, $nums);
    }
    return $count;
}
 
// Driver code
$arr = array( 2, 3, 6, 9, 10, 20 );
 
echo countPairs($arr);
 
// This code is contributed by mits    
?>

<script>
// Javascript implementation of the approach
 
// Function to return an ArrayList containing
// all the perfect squares upto n
function getPerfectSquares(n)
{
    let perfectSquares = [];
    let current = 1;
    let i = 1;
 
    // while current perfect square
    // is less than or equal to n
    while (current <= n)
    {
        perfectSquares.push(current);
        current = Math.pow(++i, 2);
    }
    return perfectSquares;
}
 
// Function to print the sum of maximum
// two elements from the array
function maxPairSum(arr)
{
    let n = arr.length
    let max;
    let secondMax;
    if (arr[0] > arr[1])
    {
        max = arr[0];
        secondMax = arr[1];
    }
    else
    {
        max = arr[1];
        secondMax = arr[0];
    }
 
    for (let i = 2; i < n; i++)
    {
        if (arr[i] > max)
        {
            secondMax = max;
            max = arr[i];
        }
        else if (arr[i] > secondMax)
        {
            secondMax = arr[$i];
        }
    }
    return (max + secondMax);
}
 
// Function to return the count of numbers that
// when added with n give a perfect square
function countPairsWith(n, perfectSquares, nums)
{
    let count = 0;
    for (let i = 0; i < perfectSquares.length; i++)
    {
        let temp = perfectSquares[i] - n;
 
        // temp > n is checked so that pairs
        // (x, y) and (y, x) don't get counted twice
        if (temp > n && nums.includes(temp))
            count++;
    }
    return count;
}
 
// Function to count the pairs whose
// sum is a perfect square
function countPairs(arr)
{
    let n = arr.length
 
    // Sum of the maximum two elements
    // from the array
    let max = maxPairSum(arr);
 
    // List of perfect squares upto max
    let perfectSquares = getPerfectSquares(max);
 
    // Contains all the array elements
    let nums = [];
    for (let i = 0; i < n; i++)
        nums.push(arr[i]);
 
    let count = 0;
    for (let i = 0; i < n; i++)
    {
 
        // Add count of the elements that when
        // added with arr[i] give a perfect square
        count += countPairsWith(arr[i], perfectSquares, nums);
    }
    return count;
}
 
// Driver code
let arr = new Array( 2, 3, 6, 9, 10, 20 );
 
document.write(countPairs(arr));
 
// This code is contributed by Saurabh jaiswal
 
</script>

2