Recuento de elementos que tienen un número impar de divisores en el rango de índice [L, R] para consultas Q

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros positivos y el número de consultas Q , cada consulta contiene dos números L y R. La tarea es contar el número de elementos en la array que tienen un número impar de divisores del índice L a R.

Ejemplos: 

Entrada: arr[] = [2, 4, 5, 6, 9], Q = 3, Query[][] = { {0, 2}, {1, 3}, {1, 4} } 
Salida: 1 1 2 
Explicación: 
1ª consulta: en 2 4 5 sólo 4 tiene un número impar de divisores. 
2ª consulta: en 4 5 6 solo 4 tiene un número impar de divisores. 
3ra consulta: en 4 5 6 9 solo 4, 9 tiene un número impar de divisores.

Entrada: arr[] = [1, 16, 5, 4, 9], Q = 2, Query[][] = { {1, 3}, {0, 2} } 
Salida: 2 1 

Enfoque ingenuo: el enfoque ingenuo es iterar sobre la array de L a R para cada consulta y contar el elemento en el rango [L, R] que tiene números impares de divisores. En caso afirmativo, cuente ese elemento para esa consulta.

Complejidad de tiempo: O(Q * N * sqrt(N)) 
Espacio auxiliar: O(1)

Enfoque eficiente: podemos observar que el número de divisores es impar solo en el caso de cuadrados perfectos. Por lo tanto, la mejor solución es verificar si el número dado es un cuadrado perfecto o no está en el rango [L, R] . A continuación se muestran los pasos: 

  1. Inicialice la array dp[] de tamaño N con valor 0 .
  2. Recorra la array dada arr[] y si algún elemento en él es un cuadrado perfecto, actualice el valor en ese índice en dp[] como 1 .
  3. Para calcular la respuesta de cada consulta de manera eficiente, calcularemos previamente la respuesta.
  4. Haremos la suma del prefijo del arreglo dp[] y para cada consulta en el rango [L, R] la respuesta estará dada por:
OddDivisorCount(L, R) = DP[R] - DP[L-1]

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function count the number of elements
// having odd number of divisors
void OddDivisorsCount(
    int n, int q, int a[],
    vector<pair<int, int> > Query)
{
    // Initialise dp[] array
    int DP[n] = { 0 };
 
    // Precomputation
    for (int i = 0; i < n; i++) {
        int x = sqrt(a[i]);
 
        if (x * x == a[i])
            DP[i] = 1;
    }
 
    // Find the Prefix Sum
    for (int i = 1; i < n; i++) {
        DP[i] = DP[i - 1] + DP[i];
    }
 
    int l, r;
 
    // Iterate for each query
    for (int i = 0; i < q; i++) {
        l = Query[i].first;
        r = Query[i].second;
 
        // Find the answer for each query
        if (l == 0) {
            cout << DP[r] << endl;
        }
        else {
            cout << DP[r] - DP[l - 1]
                 << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int N = 5;
    int Q = 3;
 
    // Given array arr[]
    int arr[] = { 2, 4, 5, 6, 9 };
 
    // Given Query
    vector<pair<int, int> > Query
        Query
        = { { 0, 2 }, { 1, 3 }, { 1, 4 } };
 
    // Function Call
    OddDivisorsCount(N, Q, arr, Query);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function count the number of elements
// having odd number of divisors
static void OddDivisorsCount(int n, int q,
                             int a[],
                             pair []Query)
{
     
    // Initialise dp[] array
    int DP[] = new int[n];
 
    // Precomputation
    for(int i = 0; i < n; i++)
    {
       int x = (int)Math.sqrt(a[i]);
        
       if (x * x == a[i])
           DP[i] = 1;
    }
     
    // Find the Prefix Sum
    for(int i = 1; i < n; i++)
    {
       DP[i] = DP[i - 1] + DP[i];
    }
     
    int l, r;
 
    // Iterate for each query
    for(int i = 0; i < q; i++)
    {
       l = Query[i].first;
       r = Query[i].second;
        
       // Find the answer for each query
       if (l == 0)
       {
           System.out.print(DP[r] + "\n");
       }
       else
       {
           System.out.print(DP[r] -
                            DP[l - 1] + "\n");
       }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    int Q = 3;
 
    // Given array arr[]
    int arr[] = { 2, 4, 5, 6, 9 };
 
    // Given Query
    pair []Query = { new pair(0, 2),
                     new pair(1, 3),
                     new pair(1, 4) };
 
    // Function Call
    OddDivisorsCount(N, Q, arr, Query);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program for the above approach
import math
 
# Function count the number of elements
# having odd number of divisors
def OddDivisorsCount(n, q, a, Query):
     
    # Initialise dp[] array
    DP = [0 for i in range(n)]
  
    # Precomputation
    for i in range(n):
        x = int(math.sqrt(a[i]));
  
        if (x * x == a[i]):
            DP[i] = 1;
  
    # Find the Prefix Sum
    for i in range(1, n):
        DP[i] = DP[i - 1] + DP[i];
  
    l = 0
    r = 0
  
    # Iterate for each query
    for i in range(q):
        l = Query[i][0];
        r = Query[i][1];
  
        # Find the answer for each query
        if (l == 0):
            print(DP[r])
        else:
            print(DP[r] - DP[l - 1])
 
# Driver code
if __name__=="__main__":
     
    N = 5;
    Q = 3;
  
    # Given array arr[]
    arr = [ 2, 4, 5, 6, 9 ]
  
    # Given Query
    Query = [ [ 0, 2 ],
              [ 1, 3 ],
              [ 1, 4 ] ]
  
    # Function call
    OddDivisorsCount(N, Q, arr, Query);
 
# This code is contributed by rutvik_56

C#

// C# program for the above approach
using System;
 
class GFG{
class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function count the number of elements
// having odd number of divisors
static void OddDivisorsCount(int n, int q,
                             int []a,
                             pair []Query)
{
     
    // Initialise []dp array
    int []DP = new int[n];
 
    // Precomputation
    for(int i = 0; i < n; i++)
    {
       int x = (int)Math.Sqrt(a[i]);
       if (x * x == a[i])
           DP[i] = 1;
    }
     
    // Find the Prefix Sum
    for(int i = 1; i < n; i++)
    {
       DP[i] = DP[i - 1] + DP[i];
    }
     
    int l, r;
 
    // Iterate for each query
    for(int i = 0; i < q; i++)
    {
       l = Query[i].first;
       r = Query[i].second;
        
       // Find the answer for each query
       if (l == 0)
       {
           Console.Write(DP[r] + "\n");
       }
       else
       {
           Console.Write(DP[r] -
                         DP[l - 1] + "\n");
       }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5;
    int Q = 3;
 
    // Given array []arr
    int []arr = { 2, 4, 5, 6, 9 };
 
    // Given Query
    pair []Query = { new pair(0, 2),
                     new pair(1, 3),
                     new pair(1, 4) };
 
    // Function Call
    OddDivisorsCount(N, Q, arr, Query);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for the above approach
 
// Function count the number of elements
// having odd number of divisors
function OddDivisorsCount(
    n, q, a,Query)
{
 
    // Initialise dp[] array
    var DP = new Array(n).fill(0);
 
    // Precomputation
    for (var i = 0; i < n; i++) {
        var x = Math.sqrt(a[i]);
 
        if (x * x == a[i])
            DP[i] = 1;
    }
 
    // Find the Prefix Sum
    for (var i = 1; i < n; i++) {
        DP[i] = DP[i - 1] + DP[i];
    }
 
    var l, r;
 
    // Iterate for each query
    for (var i = 0; i < q; i++) {
        l = Query[i][0];
        r = Query[i][1];
 
        // Find the answer for each query
        if (l == 0) {
            document.write( DP[r] + "<br>");
        }
        else {
            document.write( DP[r] - DP[l - 1]+ "<br>");
        }
    }
}
 
// Driver Code
var N = 5;
var Q = 3;
 
// Given array arr[]
var arr = [2, 4, 5, 6, 9];
 
// Given Query
var Query
    = [[0, 2 ], [1, 3 ], [1, 4 ]];
     
// Function Call
OddDivisorsCount(N, Q, arr, Query);
 
// This code is contributed by noob2000.
</script>
Producción: 

1
1
2

 

Complejidad del tiempo: 

  • Precálculo: O(N) 
  • Para cada consulta: O(1) 
     

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

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