Recuento de subarreglos que tienen exactamente K números cuadrados perfectos

Dada una array de enteros sin ordenar arr[] y un entero K . La tarea es contar el número de subarreglo con exactamente K números cuadrados perfectos
Ejemplos: 
 

Entrada: arr[] = {2, 4, 9, 3}, K = 2 
Salida:
Explicación: 
Dado que el número total de números cuadrados perfectos en la array es 2 
, los 4 subarreglos con 2 números cuadrados perfectos son: 
1. {2, 4, 9} 
2.{2, 4, 9, 3} 
3.{4, 9} 
4.{4, 9, 3}
Entrada: arr[] = {4, 2, 5}, K = 3 
Salida:
 

Enfoque simple: 
genere todos los subarreglos y cuente la cantidad de números perfectos en el subarreglo dado si el conteo es igual a K incremente el conteo para una variable ans.
Complejidad de tiempo: O(N 2 )
Enfoque eficiente: 
 

  1. Recorra la array dada arr[] y verifique si el elemento es Perfect Square o no. 
     
  2. Si el elemento actual es Perfect Square, cambie el valor de la array en ese índice a 1, de lo contrario, cambie el valor en ese índice a 0. 
     
  3. Ahora la array dada se convierte en array binaria. 
     
  4. Ahora, encuentre el conteo de subarreglo con suma igual a K en el arreglo binario anterior usando el enfoque discutido en este artículo. 
     

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

C++

// C++ program to Count of subarrays having
// exactly K perfect square numbers.
  
#include <bits/stdc++.h>
using namespace std;
  
// A utility function to check if
// the number n is perfect square
// or not
bool isPerfectSquare(long double x)
{
    // Find floating point value of
    // square root of x.
    long double sr = sqrt(x);
  
    // If square root is an integer
    return ((sr - floor(sr)) == 0);
}
  
// Function to find number of subarrays
// with sum exactly equal to k
int findSubarraySum(int arr[], int n, int K)
{
    // STL map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    unordered_map<int, int> prevSum;
  
    int res = 0;
  
    // To store the sum of element traverse
    // so far
    int currsum = 0;
  
    for (int i = 0; i < n; i++) {
  
        // Add current element to currsum
        currsum += arr[i];
  
        // If currsum = K, then a new
        // subarray is found
        if (currsum == K) {
            res++;
        }
  
        // If currsum > K then find the
        // no. of subarrays with sum
        // currsum - K and exclude those
        // subarrays
        if (prevSum.find(currsum - K)
            != prevSum.end())
            res += (prevSum[currsum - K]);
  
        // Add currsum to count of
        // different values of sum
        prevSum[currsum]++;
    }
  
    // Return the final result
    return res;
}
  
// Function to count the subarray with K
// perfect square numbers
void countSubarray(int arr[], int n, int K)
{
    // Update the array element
    for (int i = 0; i < n; i++) {
  
        // If current element is perfect
        // square then update the
        // arr[i] to 1
        if (isPerfectSquare(arr[i])) {
            arr[i] = 1;
        }
  
        // Else change arr[i] to 0
        else {
            arr[i] = 0;
        }
    }
  
    // Function Call
    cout << findSubarraySum(arr, n, K);
}
  
// Driver Code
int main()
{
    int arr[] = { 2, 4, 9, 2 };
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function Call
    countSubarray(arr, N, K);
    return 0;
}

Java

// Java program to Count of subarrays having
// exactly K perfect square numbers.
import java.util.*;
  
class GFG {
  
// A utility function to check if
// the number n is perfect square
// or not
static boolean isPerfectSquare(double x)
{
          
    // Find floating point value of
    // square root of x.
    double sr = Math.sqrt(x);
  
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
  
// Function to find number of subarrays
// with sum exactly equal to k
static int findSubarraySum(int arr[], 
                           int n, int K)
{
      
    // Map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    Map<Integer, Integer> prevSum = new HashMap<>();
  
    int res = 0;
  
    // To store the sum of element 
    // traverse so far
    int currsum = 0;
  
    for(int i = 0; i < n; i++)
    {
         
       // Add current element to currsum
       currsum += arr[i];
         
       // If currsum = K, then a new
       // subarray is found
       if (currsum == K)
       {
           res++;
       }
         
       // If currsum > K then find the
       // no. of subarrays with sum
       // currsum - K and exclude those
       // subarrays
       if (prevSum.containsKey(currsum - K))
           res += (prevSum.get(currsum - K));
         
       // Add currsum to count of
       // different values of sum
       prevSum.put(currsum, 
                   prevSum.getOrDefault(currsum, 0) + 1);
    }
      
    // Return the final result
    return res;
}
  
// Function to count the subarray with K
// perfect square numbers
static void countSubarray(int arr[], int n, int K)
{
      
    // Update the array element
    for(int i = 0; i < n; i++)
    {
          
       // If current element is perfect
       // square then update the
       // arr[i] to 1
       if (isPerfectSquare(arr[i]))
       {
           arr[i] = 1;
       }
         
       // Else change arr[i] to 0
       else 
       {
           arr[i] = 0;
       }
    }
  
    // Function Call
    System.out.println(findSubarraySum(arr, n, K));
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 4, 9, 2 };
    int K = 2;
    int N = arr.length;
  
    // Function Call
    countSubarray(arr, N, K);
}
}
  
// This code is contributed by offbeat

Python3

# Python3 program to count of subarrays 
# having exactly K perfect square numbers.
from collections import defaultdict 
import math 
  
# A utility function to check if
# the number n is perfect square
# or not
def isPerfectSquare(x):
  
    # Find floating point value of
    # square root of x.
    sr = math.sqrt(x)
  
    # If square root is an integer
    return ((sr - math.floor(sr)) == 0)
  
# Function to find number of subarrays
# with sum exactly equal to k
def findSubarraySum(arr, n, K):
  
    # STL map to store number of subarrays
    # starting from index zero having
    # particular value of sum.
    prevSum = defaultdict(int)
  
    res = 0
  
    # To store the sum of element traverse
    # so far
    currsum = 0
  
    for i in range(n):
  
        # Add current element to currsum
        currsum += arr[i]
  
        # If currsum = K, then a new
        # subarray is found
        if (currsum == K):
            res += 1
  
        # If currsum > K then find the
        # no. of subarrays with sum
        # currsum - K and exclude those
        # subarrays
        if ((currsum - K) in prevSum):
            res += (prevSum[currsum - K])
  
        # Add currsum to count of
        # different values of sum
        prevSum[currsum] += 1
  
    # Return the final result
    return res
  
# Function to count the subarray with K
# perfect square numbers
def countSubarray(arr, n, K):
  
    # Update the array element
    for i in range(n):
  
        # If current element is perfect
        # square then update the
        # arr[i] to 1
        if (isPerfectSquare(arr[i])):
            arr[i] = 1
  
        # Else change arr[i] to 0
        else:
            arr[i] = 0
  
    # Function Call
    print(findSubarraySum(arr, n, K))
  
# Driver Code
if __name__ == "__main__":
      
    arr = [ 2, 4, 9, 2 ]
    K = 2
    N = len(arr)
  
    # Function Call
    countSubarray(arr, N, K)
  
# This code is contributed by chitranayal

C#

// C# program to count of subarrays having
// exactly K perfect square numbers.
using System; 
using System.Collections; 
using System.Collections.Generic; 
  
class GFG{
      
// A utility function to check if
// the number n is perfect square
// or not
static bool isPerfectSquare(double x)
{
          
    // Find floating point value of
    // square root of x.
    double sr = Math.Sqrt(x);
  
    // If square root is an integer
    return ((sr - Math.Floor(sr)) == 0);
}
  
// Function to find number of subarrays
// with sum exactly equal to k
static int findSubarraySum(int []arr, 
                           int n, int K)
{
      
    // Map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    Dictionary<int,
               int> prevSum = new Dictionary<int, 
                                             int>(); 
                                               
    int res = 0;
  
    // To store the sum of element 
    // traverse so far
    int currsum = 0;
  
    for(int i = 0; i < n; i++)
    {
          
        // Add current element to currsum
        currsum += arr[i];
              
        // If currsum = K, then a new
        // subarray is found
        if (currsum == K)
        {
            res++;
        }
              
        // If currsum > K then find the
        // no. of subarrays with sum
        // currsum - K and exclude those
        // subarrays
        if (prevSum.ContainsKey(currsum - K))
            res += (prevSum[currsum - K]);
              
        // Add currsum to count of
        // different values of sum
        if(prevSum.ContainsKey(currsum))
        {
            prevSum[currsum]++;
        }
        else
        {
            prevSum[currsum] = 1;
        }
    }
      
    // Return the final result
    return res;
}
  
// Function to count the subarray with K
// perfect square numbers
static void countSubarray(int []arr, int n,
                                     int K)
{
      
    // Update the array element
    for(int i = 0; i < n; i++)
    {
          
        // If current element is perfect
        // square then update the
        // arr[i] to 1
        if (isPerfectSquare(arr[i]))
        {
            arr[i] = 1;
        }
              
        // Else change arr[i] to 0
        else
        {
            arr[i] = 0;
        }
    }
  
    // Function call
    Console.Write(findSubarraySum(arr, n, K));
}
  
// Driver Code
public static void Main(string[] args)
{
    int []arr = { 2, 4, 9, 2 };
    int K = 2;
    int N = arr.Length;
  
    // Function call
    countSubarray(arr, N, K);
}
}
  
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript program to Count of subarrays having
// exactly K perfect square numbers.
      
// A utility function to check if
// the number n is perfect square
// or not    
function isPerfectSquare(x)
{
  
    // Find floating point value of
    // square root of x.
    let sr = Math.sqrt(x);
    
    // If square root is an integer
    return ((sr - Math.floor(sr)) == 0);
}
  
// Function to find number of subarrays
// with sum exactly equal to k
function findSubarraySum(arr, n, k)
{
  
    // Map to store number of subarrays
    // starting from index zero having
    // particular value of sum.
    let prevSum = new Map();  
    let res = 0;
    
    // To store the sum of element 
    // traverse so far
    let currsum = 0;  
    for(let i = 0; i < n; i++)
    {
           
       // Add current element to currsum
       currsum += arr[i];
           
       // If currsum = K, then a new
       // subarray is found
       if (currsum == K)
       {
           res++;
       }
           
       // If currsum > K then find the
       // no. of subarrays with sum
       // currsum - K and exclude those
       // subarrays
       if (prevSum.has(currsum - K))
           res += (prevSum.get(currsum - K));
           
       // Add currsum to count of
       // different values of sum
       prevSum.set(currsum, 
                   prevSum.get(currsum)==null?1:prevSum.get(currsum) + 1);
    }
        
    // Return the final result
    return res;
}
  
// Function to count the subarray with K
// perfect square numbers
function countSubarray(arr, n, k)
{
  
    // Update the array element
    for(let i = 0; i < n; i++)
    {
            
       // If current element is perfect
       // square then update the
       // arr[i] to 1
       if (isPerfectSquare(arr[i]))
       {
           arr[i] = 1;
       }
           
       // Else change arr[i] to 0
       else 
       {
           arr[i] = 0;
       }
    }
    
    // Function Call
    document.write(findSubarraySum(arr, n, K));
}
  
// Driver code
let arr=[2, 4, 9, 2];
let K = 2;
let N = arr.length;
  
// Function Call
countSubarray(arr, N, K);
  
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

4

 

Complejidad temporal: O(N) 
Complejidad espacial: O(N)
 

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array

Publicación traducida automáticamente

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