Consultas para contar Números Mágicos Compuestos de un rango dado [L, R]

Dadas dos arrays L[] y R[] de tamaños Q , la tarea es encontrar el número de números mágicos compuestos, es decir, números que son tanto números compuestos como números mágicos del rango [L[i], R[i] ] ( 0 ≤ yo < Q).

Ejemplos: 

Entrada: Q = 1, L[] = {10}, R[] = {100}
Salida: 8
Explicación: Números en el rango [L[0], R[0]] que son tanto números compuestos como mágicos son {10, 28, 46, 55, 64, 82, 91, 100}.

Entrada: Q = 1, L[] = {1200}, R[] = {1300}
Salida: 9
Explicación: Números en el rango [L[0], R[0]] que son tanto números compuestos como mágicos son {1207, 1216, 1225, 1234, 1243, 1252, 1261, 1270, 1288}.

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar todos los números en el rango [L[i], R[i]] (0 ≤ i < Q) y para cada número, verifique si es compuesto así como un número mágico o no. 

Complejidad de Tiempo: O(Q * N ^3/2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, calcule previamente y almacene los recuentos de números mágicos compuestos en una array en un cierto rango. Esto optimiza las complejidades computacionales de cada consulta a O(1). Siga los pasos a continuación para resolver el problema:

1. Inicialice una array de enteros dp[] tal que dp[i] almacene el conteo de Números Mágicos Compuestos hasta i .
2. Recorra el rango [1, 10 ⁶ ] y para cada número en el rango, verifique si es un Número Mágico Compuesto o no. Si se determina que es cierto, actualice dp[i ] con dp[i – 1] + 1 . De lo contrario, actualice dp[i] con dp[i – 1]
3. Recorra las arrays L[] y R[] simultáneamente e imprima dp[R[i]] – dp[L[i] – 1] como la respuesta requerida.

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

// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
 
// Check if a number is magic
// number or not
bool isMagic(int num)
{
    return (num % 9 == 1);
}
 
// Check number is composite
// number or not
bool isComposite(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
 
    if (n <= 3)
        return false;
 
    // Check if the number is
    // a multiple of 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return true;
 
    // Check for multiples of remaining primes
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return true;
 
    return false;
}
 
// Function to find Composite Magic
// Numbers in given ranges
void find(int L[], int R[], int q)
{
    // dp[i]: Stores the count of
    // composite Magic numbers up to i
    int dp[1000005];
 
    dp[0] = 0;
    dp[1] = 0;
 
    // Traverse in the range [1, 1e5)
    for (int i = 1; i < 1000005; i++) {
 
        // Check if number is Composite number
        // as well as a Magic number or not
        if (isComposite(i) && isMagic(i)) {
            dp[i] = dp[i - 1] + 1;
        }
 
        else
            dp[i] = dp[i - 1];
    }
 
    // Print results for each query
    for (int i = 0; i < q; i++)
        cout << dp[R[i]] - dp[L[i] - 1] << endl;
}
 
// Driver Code
int main()
{
    int L[] = { 10, 3 };
    int R[] = { 100, 2279 };
    int Q = 2;
 
    find(L, R, Q);
    return 0;
}

// Java program to implement
// the above approach
class GFG
{
     
    // Check if a number is magic
    // number or not
    static boolean isMagic(int num)
    {
        return (num % 9 == 1);
    }
     
    // Check number is composite
    // number or not
    static boolean isComposite(int n)
    {
        // Corner cases
        if (n <= 1)
            return false;
     
        if (n <= 3)
            return false;
     
        // Check if the number is
        // a multiple of 2 or 3
        if (n % 2 == 0 || n % 3 == 0)
            return true;
     
        // Check for multiples of remaining primes
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return true;
     
        return false;
    }
     
    // Function to find Composite Magic
    // Numbers in given ranges
    static void find(int L[], int R[], int q)
    {
        // dp[i]: Stores the count of
        // composite Magic numbers up to i
        int dp[] = new int[1000005];
     
        dp[0] = 0;
        dp[1] = 0;
     
        // Traverse in the range [1, 1e5)
        for (int i = 1; i < 1000005; i++)
        {
     
            // Check if number is Composite number
            // as well as a Magic number or not
            if (isComposite(i) && isMagic(i) == true)
            {
                dp[i] = dp[i - 1] + 1;
            }
     
            else
                dp[i] = dp[i - 1];
        }
     
        // Print results for each query
        for (int i = 0; i < q; i++)
            System.out.println(dp[R[i]] - dp[L[i] - 1]);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int L[] = { 10, 3 };
        int R[] = { 100, 2279 };
        int Q = 2;
     
        find(L, R, Q);
    }
}
 
// This code is contributed by AnkThon

# Python3 program to implement
# the above approach
 
# Check if a number is magic
# number or not
def isMagic(num):
     
    return (num % 9 == 1)
 
# Check number is composite
# number or not
def isComposite(n):
     
    # Corner cases
    if (n <= 1):
        return False
 
    if (n <= 3):
        return False
 
    # Check if the number is
    # a multiple of 2 or 3
    if (n % 2 == 0 or n % 3 == 0):
        return True
 
    # Check for multiples of remaining primes
    for i in range(5, n + 1, 6):
        if i * i > n + 1:
            break
         
        if (n % i == 0 or n % (i + 2) == 0):
            return True
 
    return False
 
# Function to find Composite Magic
# Numbers in given ranges
def find(L, R, q):
     
    # dp[i]: Stores the count of
    # composite Magic numbers up to i
    dp = [0] * 1000005
 
    dp[0] = 0
    dp[1] = 0
 
    # Traverse in the range [1, 1e5)
    for i in range(1, 1000005):
         
        # Check if number is Composite number
        # as well as a Magic number or not
        if (isComposite(i) and isMagic(i)):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
 
    # Print results for each query
    for i in range(q):
        print(dp[R[i]] - dp[L[i] - 1])
 
# Driver Code
if __name__ == '__main__':
     
    L = [ 10, 3 ]
    R = [ 100, 2279 ]
    Q = 2
 
    find(L, R, Q)
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach 
using System;
 
class GFG{
      
// Check if a number is magic
// number or not
static bool isMagic(int num)
{
    return (num % 9 == 1);
}
  
// Check number is composite
// number or not
static bool isComposite(int n)
{
     
    // Corner cases
    if (n <= 1)
        return false;
  
    if (n <= 3)
        return false;
  
    // Check if the number is
    // a multiple of 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return true;
  
    // Check for multiples of remaining primes
    for(int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return true;
  
    return false;
}
  
// Function to find Composite Magic
// Numbers in given ranges
static void find(int[] L, int[] R, int q)
{
     
    // dp[i]: Stores the count of
    // composite Magic numbers up to i
    int[] dp = new int[1000005];
  
    dp[0] = 0;
    dp[1] = 0;
  
    // Traverse in the range [1, 1e5)
    for(int i = 1; i < 1000005; i++)
    {
         
        // Check if number is Composite number
        // as well as a Magic number or not
        if (isComposite(i) && isMagic(i) == true)
        {
            dp[i] = dp[i - 1] + 1;
        }
  
        else
            dp[i] = dp[i - 1];
    }
  
    // Print results for each query
    for(int i = 0; i < q; i++)
        Console.WriteLine(dp[R[i]] - dp[L[i] - 1]);
}
  
// Driver Code
public static void Main ()
{
    int[] L = { 10, 3 };
    int[] R = { 100, 2279 };
    int Q = 2;
  
    find(L, R, Q);
}
}
 
// This code is contributed by susmitakundugoaldanga

<script>
 
// JavaScript program to implement
// the above approach
     
    // Check if a number is magic
    // number or not
    function isMagic(num)
    {
        return (num % 9 == 1);
    }
      
    // Check number is composite
    // number or not
    function isComposite(n)
    {
        // Corner cases
        if (n <= 1)
            return false;
      
        if (n <= 3)
            return false;
      
        // Check if the number is
        // a multiple of 2 or 3
        if (n % 2 == 0 || n % 3 == 0)
            return true;
      
        // Check for multiples of remaining primes
        for (let i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return true;
      
        return false;
    }
      
    // Function to find Composite Magic
    // Numbers in given ranges
    function find(L, R, q)
    {
        // dp[i]: Stores the count of
        // composite Magic numbers up to i
        let dp = [];
      
        dp[0] = 0;
        dp[1] = 0;
      
        // Traverse in the range [1, 1e5)
        for (let i = 1; i < 1000005; i++)
        {
      
            // Check if number is Composite number
            // as well as a Magic number or not
            if (isComposite(i) && isMagic(i) == true)
            {
                dp[i] = dp[i - 1] + 1;
            }
      
            else
                dp[i] = dp[i - 1];
        }
      
        // Print results for each query
        for (let i = 0; i < q; i++)
            document.write(dp[R[i]] - dp[L[i] - 1] + "<br/>");
    }
      
 
      
// Driver code
         
        let L = [ 10, 3 ];
        let R = [100, 2279 ];
        let Q = 2;
      
        find(L, R, Q);
 
</script>

8
198

Complejidad de Tiempo: O(N ^3/2 )
Espacio Auxiliar: O(N )