Consultas para contar números enteros en un rango [L, R] tales que su suma de dígitos sea primo y divisible por K

Posted on by Rudeus Greyrat

Dadas Q consultas y un entero K donde cada consulta consta de un rango [L, R] y la tarea es encontrar el número de enteros en el rango dado cuya suma de dígitos es primo y divisible por K .
Ejemplo: 
 

Input: Q = { {1, 11},
      {5, 15},
      {2, 24} } 
K = 2
Output: 
2
1
3
Explanation:
Query 1: 2 and 11 are the only 
numbers in the given range whose 
digit sum is prime and divisible by K.
Query 2: 11 is the only number.
Query 3: 2, 11 and 20.

Input: Q = { {2, 17},
             {3, 24} }
K = 3
Output:
2
3

Acercarse: 
 

  • Primero calcule previamente todos los primos hasta el valor máximo posible de R entre todos los rangos dados, diga maxVal usando Sieve of Eratosthenes .
  • Luego marque todos los números enteros desde 1 hasta maxVal que sean divisibles por K y sean primos.
  • Tome la suma del prefijo de la array marcada.
  • Responda las consultas dadas por prefijo [derecha] – prefijo [izquierda – 1] .

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int maxSize = 1e5 + 1;
bool isPrime[maxSize];
int prefix[maxSize];
 
// Function to return the
// digit sum of num
int digitSum(int num)
{
    int s = 0;
    while (num != 0) {
        s = s + num % 10;
        num = num / 10;
    }
    return s;
}
 
// Sieve Function to generate
// all primes opto maxSize
void sieveOfEratosthenes()
{
    for (int i = 2; i < maxSize; i++) {
        isPrime[i] = true;
    }
 
    for (int i = 2; i * i <= maxSize; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < maxSize; j += i) {
                isPrime[j] = false;
            }
        }
    }
}
 
// Pre-Computation till maxSize
// and for a given K
void precompute(int k)
{
    sieveOfEratosthenes();
    for (int i = 1; i < maxSize; i++) {
        // Getting Digit Sum
        int sum = digitSum(i);
        // Check if the digit sum
        // is prime and divisible by k
        if (isPrime[sum] == true && sum % k == 0) {
            prefix[i]++;
        }
    }
 
    // Taking Prefix Sum
    for (int i = 1; i < maxSize; i++) {
        prefix[i] = prefix[i] + prefix[i - 1];
    }
}
 
// Function to perform the queries
void performQueries(int k, int q,
                    vector<vector<int> >& query)
{
    // Precompute the results
    precompute(k);
 
    vector<int> ans;
    for (int i = 0; i < q; i++) {
        int l = query[i][0], r = query[i][1];
 
        // Getting count of range in range [L, R]
        int cnt = prefix[r] - prefix[l - 1];
        cout << cnt << endl;
    }
}
 
// Driver code
int main()
{
    vector<vector<int> > query = { { 1, 11 },
                                   { 5, 15 },
                                   { 2, 24 } };
    int k = 2, q = query.size();
    performQueries(k, q, query);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
    static final int maxSize = (int)1e5 + 1;
    static boolean isPrime[] = new boolean[maxSize];
    static int prefix[] = new int[maxSize];
     
    // Function to return the
    // digit sum of num
    static int digitSum(int num)
    {
        int s = 0;
        while (num != 0)
        {
            s = s + num % 10;
            num = num / 10;
        }
        return s;
    }
     
    // Sieve Function to generate
    // all primes opto maxSize
    static void sieveOfEratosthenes()
    {
        for (int i = 2; i < maxSize; i++)
        {
            isPrime[i] = true;
        }
     
        for (int i = 2; i * i <= maxSize; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i;
                         j < maxSize; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }
    }
     
    // Pre-Computation till maxSize
    // and for a given K
    static void precompute(int k)
    {
        sieveOfEratosthenes();
         
        for (int i = 1; i < maxSize; i++)
        {
             
            // Getting Digit Sum
            int sum = digitSum(i);
             
            // Check if the digit sum
            // is prime and divisible by k
            if (isPrime[sum] == true &&
                        sum % k == 0)
            {
                prefix[i]++;
            }
        }
     
        // Taking Prefix Sum
        for (int i = 1; i < maxSize; i++)
        {
            prefix[i] = prefix[i] +
                        prefix[i - 1];
        }
    }
     
    // Function to perform the queries
    static void performQueries(int k, int q,
                               int query[][])
    {
        // Precompute the results
        precompute(k);
         
        for (int i = 0; i < q; i++)
        {
            int l = query[i][0], r = query[i][1];
     
            // Getting count of range in range [L, R]
            int cnt = prefix[r] - prefix[l - 1];
             
            System.out.println(cnt);
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int query[][] = { { 1, 11 },
                          { 5, 15 },
                          { 2, 24 } };
        int k = 2, q = query.length;
        performQueries(k, q, query);
    }
}
 
// This Code is contributed by AnkitRai01

Python3

# Python3 implementation of the approach
from math import sqrt
 
maxSize = 10 ** 5 + 1;
isPrime = [0] * maxSize;
prefix = [0] * maxSize;
 
# Function to return the
# digit sum of num
def digitSum(num) :
     
    s = 0;
    while (num != 0) :
        s = s + num % 10;
        num = num // 10;
 
    return s;
 
# Sieve Function to generate
# all primes opto maxSize
def sieveOfEratosthenes() :
 
    for i in range(2, maxSize) :
        isPrime[i] = True;
 
    for i in range(2, int(sqrt(maxSize)) + 1) :
        if (isPrime[i]) :
            for j in range(i * i, maxSize, i) :
                isPrime[j] = False;
         
# Pre-Computation till maxSize
# and for a given K
def precompute(k) :
 
    sieveOfEratosthenes();
     
    for i in range(1, maxSize) :
         
        # Getting Digit Sum
        sum = digitSum(i);
         
        # Check if the digit sum
        # is prime and divisible by k
        if (isPrime[sum] == True and
                    sum % k == 0) :
            prefix[i] += 1;
 
    # Taking Prefix Sum
    for i in range(1, maxSize) :
        prefix[i] = prefix[i] + prefix[i - 1];
 
# Function to perform the queries
def performQueries(k, q, query) :
 
    # Precompute the results
    precompute(k);
 
    for i in range(q) :
        l = query[i][0]; r = query[i][1];
 
        # Getting count of range in range [L, R]
        cnt = prefix[r] - prefix[l - 1];
        print(cnt);
         
# Driver code
if __name__ == "__main__" :
 
    query = [ [ 1, 11 ],
              [ 5, 15 ],
              [ 2, 24 ] ];
             
    k = 2; q = len(query);
    performQueries(k, q, query);
     
# This code is contributed by kanugargng

C#

// C# implementation of the above approach
using System;
     
class GFG
{
    static readonly int maxSize = (int)1e5 + 1;
    static Boolean []isPrime = new Boolean[maxSize];
    static int []prefix = new int[maxSize];
     
    // Function to return the
    // digit sum of num
    static int digitSum(int num)
    {
        int s = 0;
        while (num != 0)
        {
            s = s + num % 10;
            num = num / 10;
        }
        return s;
    }
     
    // Sieve Function to generate
    // all primes opto maxSize
    static void sieveOfEratosthenes()
    {
        for (int i = 2; i < maxSize; i++)
        {
            isPrime[i] = true;
        }
     
        for (int i = 2; i * i <= maxSize; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i;
                         j < maxSize; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }
    }
     
    // Pre-Computation till maxSize
    // and for a given K
    static void precompute(int k)
    {
        sieveOfEratosthenes();
         
        for (int i = 1; i < maxSize; i++)
        {
             
            // Getting Digit Sum
            int sum = digitSum(i);
             
            // Check if the digit sum
            // is prime and divisible by k
            if (isPrime[sum] == true &&
                        sum % k == 0)
            {
                prefix[i]++;
            }
        }
     
        // Taking Prefix Sum
        for (int i = 1; i < maxSize; i++)
        {
            prefix[i] = prefix[i] +
                        prefix[i - 1];
        }
    }
     
    // Function to perform the queries
    static void performQueries(int k, int q,
                               int [,]query)
    {
        // Precompute the results
        precompute(k);
         
        for (int i = 0; i < q; i++)
        {
            int l = query[i, 0], r = query[i, 1];
     
            // Getting count of range in range [L, R]
            int cnt = prefix[r] - prefix[l - 1];
             
            Console.WriteLine(cnt);
        }
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int [,]query = {{ 1, 11 },
                        { 5, 15 },
                        { 2, 24 }};
        int k = 2, q = query.GetLength(0);
        performQueries(k, q, query);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript implementation of the approach
 
var maxSize = parseInt(1e5 + 1);
var isPrime = Array.from({length: maxSize},
(_, i) => false);
var prefix = Array.from({length: maxSize},
(_, i) => 0);
 
// Function to return the
// digit sum of num
function digitSum(num)
{
    var s = 0;
    while (num != 0)
    {
        s = s + num % 10;
        num = parseInt(num / 10);
    }
    return s;
}
 
// Sieve Function to generate
// all primes opto maxSize
function sieveOfEratosthenes()
{
    for (i = 2; i < maxSize; i++)
    {
        isPrime[i] = true;
    }
 
    for (i = 2; i * i <= maxSize; i++)
    {
        if (isPrime[i])
        {
            for (j = i * i;
                     j < maxSize; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}
 
// Pre-Computation till maxSize
// and for a given K
function precompute(k)
{
    sieveOfEratosthenes();
     
    for (i = 1; i < maxSize; i++)
    {
         
        // Getting Digit Sum
        var sum = digitSum(i);
         
        // Check if the digit sum
        // is prime and divisible by k
        if (isPrime[sum] == true &&
                    sum % k == 0)
        {
            prefix[i]++;
        }
    }
 
    // Taking Prefix Sum
    for (i = 1; i < maxSize; i++)
    {
        prefix[i] = prefix[i] +
                    prefix[i - 1];
    }
}
 
// Function to perform the queries
function performQueries(k , q, query)
{
    // Precompute the results
    precompute(k);
     
    for (i = 0; i < q; i++)
    {
        var l = query[i][0], r = query[i][1];
 
        // Getting count of range in range [L, R]
        var cnt = prefix[r] - prefix[l - 1];
         
        document.write(cnt+"<br>");
    }
}
 
// Driver code
var query = [ [ 1, 11 ],
              [ 5, 15 ],
              [ 2, 24 ] ];
var k = 2, q = query.length;
performQueries(k, q, query);
 
// This code contributed by shikhasingrajput
 
</script>
Producción: 

2
1
3

 

Publicación traducida automáticamente

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