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: 4
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: 0
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:
- Recorra la array dada arr[] y verifique si el elemento es Perfect Square o no.
- 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.
- Ahora la array dada se convierte en array binaria.
- 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