Cuente los elementos de la array cuyos cuadrados perfectos están presentes en la array dada

Dada una array arr[] , la tarea es encontrar la cantidad de elementos de la array cuyos cuadrados ya están presentes en la array.

Ejemplos:

Entrada: arr[] = {2, 4, 5, 20, 16}
Salida: 2
Explicación:
{2, 4} tiene sus cuadrados {4, 16} presentes en la array.

Entrada: arr[] = {1, 30, 3, 8, 64}
Salida : 2
Explicación:
{1, 8} tiene sus cuadrados {1, 64} presentes en la array.

Enfoque ingenuo: siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos count , para almacenar el conteo requerido.
• Atraviese la array y, para todos y cada uno de los elementos de la array, realice las siguientes operaciones:
  • Recorra la array y busque si el cuadrado del elemento actual está presente en la array.
  • Si el cuadrado encontrado incrementa la cuenta.
• Imprima el conteo como la respuesta.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of elements whose
// squares are already present int the array
void countSquares(int arr[], int N)
{
    // Stores the required count
    int count = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Square of the element
        int square = arr[i] * arr[i];
 
        // Traverse the array
        for (int j = 0; j < N; j++) {
 
            // Check whether the value
            // is equal to square
            if (arr[j] == square) {
 
                // Increment count
                count = count + 1;
            }
        }
    }
 
    // Print the count
    cout << count;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 4, 5, 20, 16 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    countSquares(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the count of elements whose
// squares are already present int the array
static void countSquares(int arr[], int N)
{
   
    // Stores the required count
    int count = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
        // Square of the element
        int square = arr[i] * arr[i];
 
        // Traverse the array
        for (int j = 0; j < N; j++)
        {
 
            // Check whether the value
            // is equal to square
            if (arr[j] == square)
            {
 
                // Increment count
                count = count + 1;
            }
        }
    }
 
    // Print the count
    System.out.print(count);
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given array
    int arr[] = { 2, 4, 5, 20, 16 };
 
    // Size of the array
    int N = arr.length;
    countSquares(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

# Python program for the above approach
 
# Function to find the count of elements whose
# squares are already present the array
def countSquares(arr, N):
   
    # Stores the required count
    count = 0;
 
    # Traverse the array
    for i in range(N):
 
        # Square of the element
        square = arr[i] * arr[i];
 
        # Traverse the array
        for j in range(N):
 
            # Check whether the value
            # is equal to square
            if (arr[j] == square):
               
                # Increment count
                count = count + 1;
 
    # Print count
    print(count);
 
# Driver Code
if __name__ == '__main__':
   
    # Given array
    arr = [2, 4, 5, 20, 16];
 
    # Size of the array
    N = len(arr);
    countSquares(arr, N);
 
# This code is contributed by shikhasingrajput

// C# program of the above approach
using System;
 
class GFG{
     
// Function to find the count of elements whose
// squares are already present int the array
static void countSquares(int[] arr, int N)
{
     
    // Stores the required count
    int count = 0;
     
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // Square of the element
        int square = arr[i] * arr[i];
   
        // Traverse the array
        for(int j = 0; j < N; j++)
        {
             
            // Check whether the value
            // is equal to square
            if (arr[j] == square)
            {
                 
                // Increment count
                count = count + 1;
            }
        }
    }
     
    // Print the count
    Console.WriteLine(count);
}   
 
// Driver code   
static void Main()
{
     
    // Given array
    int[] arr = { 2, 4, 5, 20, 16 };
     
    // Size of the array
    int N = arr.Length;
     
    countSquares(arr, N);
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript program for the above approach
 
// Function to find the count of elements whose
// squares are already present int the array
function countSquares(arr, N)
{
    // Stores the required count
    var count = 0;
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
 
        // Square of the element
        var square = arr[i] * arr[i];
 
        // Traverse the array
        for (var j = 0; j < N; j++) {
 
            // Check whether the value
            // is equal to square
            if (arr[j] == square) {
 
                // Increment count
                count = count + 1;
            }
        }
    }
 
    // Print the count
    document.write( count);
}
 
// Driver Code
// Given array
var arr = [2, 4, 5, 20, 16];
// Size of the array
var N = arr.length;
countSquares(arr, N);
 
</script>

2

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

Enfoque eficiente: la idea óptima es utilizar unordered_map para mantener el recuento de elementos visitados y actualizar el recuento de variables en consecuencia. A continuación se muestran los pasos:

• Inicialice un mapa para almacenar la frecuencia de los elementos de la array e inicialice una variable, por ejemplo, contar .
• Recorra la array y para cada elemento, incremente su conteo en el Mapa.
• Recorra nuevamente la array y para cada elemento verifique la frecuencia del cuadrado del elemento en el mapa y agréguelo a la variable conteo.
• Imprime el conteo como el número de elementos cuyo cuadrado ya está presente en la array.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of elements whose
// squares is already present int the array
int countSquares(int arr[], int N)
{
    // Stores the count of array elements
    int count = 0;
 
    // Stores frequency of visited elements
    unordered_map<int, int> m;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        m[arr[i]] = m[arr[i]] + 1;
    }
 
    for (int i = 0; i < N; i++) {
 
        // Square of the element
        int square = arr[i] * arr[i];
 
        // Update the count
        count += m[square];
    }
 
    // Print the count
    cout << count;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 4, 5, 20, 16 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countSquares(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to find the count of elements whose
// squares is already present int the array
static void countSquares(int arr[], int N)
{
   
    // Stores the count of array elements
    int count = 0;
 
    // Stores frequency of visited elements
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
        if(mp.containsKey(arr[i]))
        {
            mp.put(arr[i], mp.get(arr[i]) + 1);
        }
        else
        {
            mp.put(arr[i], 1);
        }
    }
    for (int i = 0; i < N; i++)
    {
 
        // Square of the element
        int square = arr[i] * arr[i];
 
        // Update the count
        count += mp.containsKey(square)?mp.get(square):0;
    }
 
    // Print the count
    System.out.print(count);
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given array
    int arr[] = { 2, 4, 5, 20, 16 };
 
    // Size of the array
    int N = arr.length;
 
    // Function Call
    countSquares(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to find the count of elements whose
# squares is already present int the array
def countSquares( arr, N):
 
    # Stores the count of array elements
    count = 0;
 
    # Stores frequency of visited elements
    m = defaultdict(int);
 
    # Traverse the array
    for i in range(N):
        m[arr[i]] = m[arr[i]] + 1
 
    for i in range( N ):
 
        # Square of the element
        square = arr[i] * arr[i]
 
        # Update the count
        count += m[square]
 
    # Print the count
    print(count)
 
# Driver Code
if __name__ == "__main__":
   
    # Given array
    arr = [ 2, 4, 5, 20, 16 ]
 
    # Size of the array
    N = len(arr)
 
    # Function Call
    countSquares(arr, N);
 
# This code is contributed by chitranayal.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
   
// Function to find the count of elements whose
// squares is already present int the array
static void countSquares(int []arr, int N)
{
   
    // Stores the count of array elements
    int count = 0;
 
    // Stores frequency of visited elements
    Dictionary<int, int> mp =
                    new Dictionary<int, int>();
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
        if(mp.ContainsKey(arr[i]))
        {
            mp.Add(arr[i], mp[arr[i]] + 1);
        }
        else
        {
            mp.Add(arr[i], 1);
        }
    }
    for (int i = 0; i < N; i++)
    {
        // Square of the element
        int square = arr[i] * arr[i];
 
        // Update the count
        count += mp.ContainsKey(square)?mp[square]:0;
    }
   
    // Print the count
    Console.Write(count);
}
 
// Driver Code
public static void Main()
{
    // Given array
    int []arr = { 2, 4, 5, 20, 16 };
 
    // Size of the array
    int N = arr.Length;
 
    // Function Call
    countSquares(arr, N);
}
}
 
// This code is contributed by Samim Hossain Mondal

<script>
 
// Javascript program for the above approach
 
// Function to find the count of elements whose
// squares is already present int the array
function countSquares(arr, N)
{
    // Stores the count of array elements
    var count = 0;
 
    // Stores frequency of visited elements
    var m = new Map();
 
    // Traverse the array
    for (var i = 0; i < N; i++) {
        if(m.has(arr[i]))
            m.set(arr[i], m.get(arr[i])+1)
        else   
            m.set(arr[i], 1);
    }
 
    for (var i = 0; i < N; i++) {
 
        // Square of the element
        var square = arr[i] * arr[i];
 
        // Update the count
        if(m.has(square))
            count += m.get(square);
    }
 
    // Print the count
    document.write( count);
}
 
// Driver Code
// Given array
var arr = [2, 4, 5, 20, 16];
// Size of the array
var N = arr.length;
// Function Call
countSquares(arr, N);
 
</script>

2

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