Cuente números divisibles por K en un rango con suma de dígitos de Fibonacci para consultas Q

Dada una array arr[][] que contiene consultas Q y un número entero K donde cada consulta consta de un rango [L, R] , la tarea es encontrar el recuento de números enteros en el rango dado cuya suma de dígitos es un número de Fibonacci y divisible por k _
Ejemplos: 
 

Entrada: arr[][] = { {1, 11}, {5, 15}, {2, 24} }, K = 2 
Salida: 3 2 5 
Explicación: 
Para la consulta 1: 2, 8 y 11 son los números en el rango dado cuya suma de dígitos es Fibonacci y divisible por K. 
Para la consulta 2: 8 y 11 son los números en el rango dado cuya suma de dígitos es Fibonacci y divisible por K. 
Para la consulta 3: 2, 8, 11, 17 y 20 son los números en el rango dado cuya suma de dígitos es Fibonacci y divisible por K.
Entrada: arr[][] = { {2, 17}, {3, 24} }, K = 3 
Salida: 4 4 
Explicación: 
Para consulta 1: 2, 8, 11 y 17 son los números en el rango dado cuya suma de dígitos es Fibonacci y divisible por K. 
Para la consulta 2: 8, 11, 17 y 20 son los números en el rango dado cuya suma de dígitos es Fibonacci y divisible por K. 
 

Enfoque: La idea es usar hash para precalcular y almacenar los Nodes de Fibonacci hasta el valor máximo en el rango dado, para que la verificación sea fácil y eficiente (en tiempo O(1)). 
 

  • Después del cálculo previo, marque todos los números enteros desde 1 hasta maxVal que sean divisibles por K y sean fibonacci.
  • Encuentre 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++ program to count the integers
// in a range [L, R] such that
// their digit sum is Fibonacci
// and divisible by K
 
#include <bits/stdc++.h>
using namespace std;
 
const int maxSize = 1e5 + 5;
bool isFib[maxSize];
int prefix[maxSize];
 
// Function to return the
// digit sum of a number
int digitSum(int num)
{
    int s = 0;
    while (num != 0) {
        s = s + num % 10;
        num = num / 10;
    }
    return s;
}
 
// Function to generate all the Fibonacci
// numbers upto maxSize
void generateFibonacci()
{
    memset(isFib, false, sizeof(isFib));
 
    // Adding the first two Fibonacci
    // numbers in the set
    int prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
 
    // Computing the remaining Fibonacci
    // numbers based on the previous
    // two Fibonacci numbers
    while (curr < maxSize) {
        int temp = curr + prev;
        isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
}
 
// Pre-Computation till maxSize
// and for a given K
void precompute(int k)
{
    generateFibonacci();
 
    for (int i = 1; i < maxSize; i++) {
 
        // Getting the digit sum
        int sum = digitSum(i);
 
        // Check if the digit sum
        // is Fibonacci and divisible by k
        if (isFib[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;
 
    // Iterating through the queries
    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 program to count the integers
// in a range [L, R] such that
// their digit sum is Fibonacci
// and divisible by K
import java.util.*;
 
class GFG{
  
static int maxSize = (int) (1e5 + 5);
static boolean []isFib  = new boolean[maxSize];
static int []prefix = new int[maxSize];
  
// Function to return the
// digit sum of a number
static int digitSum(int num)
{
    int s = 0;
    while (num != 0) {
        s = s + num % 10;
        num = num / 10;
    }
    return s;
}
  
// Function to generate all the Fibonacci
// numbers upto maxSize
static void generateFibonacci()
{
    Arrays.fill(isFib, false);
  
    // Adding the first two Fibonacci
    // numbers in the set
    int prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
  
    // Computing the remaining Fibonacci
    // numbers based on the previous
    // two Fibonacci numbers
    while (curr < maxSize) {
        int temp = curr + prev;
        if(temp < maxSize)
            isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
}
  
// Pre-Computation till maxSize
// and for a given K
static void precompute(int k)
{
    generateFibonacci();
  
    for (int i = 1; i < maxSize; i++) {
  
        // Getting the digit sum
        int sum = digitSum(i);
  
        // Check if the digit sum
        // is Fibonacci and divisible by k
        if (isFib[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);
 
    // Iterating through the queries
    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.print(cnt +"\n");
    }
}
  
// 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 Princi Singh

Python3

# Python 3 program to count the integers
# in a range [L, R] such that
# their digit sum is Fibonacci
# and divisible by K
maxSize = 100005
isFib = [False]*(maxSize)
prefix = [0]*maxSize
 
# Function to return the
# digit sum of a number
def digitSum(num):
    s = 0
    while (num != 0):
        s = s + num % 10
        num = num // 10
     
    return s
 
# Function to generate all the Fibonacci
# numbers upto maxSize
def generateFibonacci():
 
    global isFib
 
    # Adding the first two Fibonacci
    # numbers in the set
    prev = 0
    curr = 1
    isFib[prev] = True
    isFib[curr] = True
 
    # Computing the remaining Fibonacci
    # numbers based on the previous
    # two Fibonacci numbers
    while (curr < maxSize):
        temp = curr + prev
        if temp < maxSize:
            isFib[temp] = True
        prev = curr
        curr = temp
 
# Pre-Computation till maxSize
# and for a given K
def precompute(k):
 
    generateFibonacci()
    global prefix
     
    for i in range(1, maxSize):
 
        # Getting the digit sum
        sum = digitSum(i)
 
        # Check if the digit sum
        # is Fibonacci and divisible by k
        if (isFib[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)
 
    # Iterating through the queries
    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 chitranayal

C#

// C# program to count the integers
// in a range [L, R] such that
// their digit sum is Fibonacci
// and divisible by K
using System;
 
class GFG{
   
static int maxSize = (int) (1e5 + 5);
static bool []isFib  = new bool[maxSize];
static int []prefix = new int[maxSize];
   
// Function to return the
// digit sum of a number
static int digitSum(int num)
{
    int s = 0;
    while (num != 0) {
        s = s + num % 10;
        num = num / 10;
    }
    return s;
}
   
// Function to generate all the Fibonacci
// numbers upto maxSize
static void generateFibonacci()
{
 
    // Adding the first two Fibonacci
    // numbers in the set
    int prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
   
    // Computing the remaining Fibonacci
    // numbers based on the previous
    // two Fibonacci numbers
    while (curr < maxSize) {
        int temp = curr + prev;
        if(temp < maxSize)
            isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
}
   
// Pre-Computation till maxSize
// and for a given K
static void precompute(int k)
{
    generateFibonacci();
   
    for (int i = 1; i < maxSize; i++) {
   
        // Getting the digit sum
        int sum = digitSum(i);
   
        // Check if the digit sum
        // is Fibonacci and divisible by k
        if (isFib[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);
  
    // Iterating through the queries
    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.Write(cnt +"\n");
    }
}
   
// 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  program to count the integers
// in a range [L, R] such that
// their digit sum is Fibonacci
// and divisible by K
 
let maxSize = (1e5 + 5);
let isFib  = Array.from({length: maxSize}, (_, i) => 0);
let prefix = Array.from({length: maxSize}, (_, i) => 0);
    
// Function to return the
// digit sum of a number
function digitSum(num)
{
    let s = 0;
    while (num != 0) {
        s = s + num % 10;
        num = Math.floor(num / 10);
    }
    return s;
}
    
// Function to generate all the Fibonacci
// numbers upto maxSize
function generateFibonacci()
{
    isFib = Array.from({length: maxSize}, (_, i) => false);
    
    // Adding the first two Fibonacci
    // numbers in the set
    let prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
    
    // Computing the remaining Fibonacci
    // numbers based on the previous
    // two Fibonacci numbers
    while (curr < maxSize) {
        let temp = curr + prev;
        if(temp < maxSize)
            isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
}
    
// Pre-Computation till maxSize
// and for a given K
function precompute(k)
{
    generateFibonacci();
    
    for (let i = 1; i < maxSize; i++) {
    
        // Getting the digit sum
        let sum = digitSum(i);
    
        // Check if the digit sum
        // is Fibonacci and divisible by k
        if (isFib[sum] == true
            && sum % k == 0) {
            prefix[i]++;
        }
    }
    
    // Taking Prefix Sum
    for (let 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);
   
    // Iterating through the queries
    for (let i = 0; i < q; i++) {
    
        let l = query[i][0],
            r = query[i][1];
    
        // Getting count of range
        // in range [L, R]
        let cnt = prefix[r]
                  - prefix[l - 1];
        document.write(cnt +"<br/>");
    }
}
 
// Driver code
      let query
        = [[ 1, 11 ],
            [ 5, 15 ],
            [ 2, 24 ]];
    let k = 2, q = query.length;
    
    performQueries(k, q, query);
 
 // This code is contributed by sanjoy_62.                                                                              
</script>
Producción

3
2
5

Complejidad del tiempo: O(maxSize,q)

Espacio auxiliar: O (tamaño máximo)

Publicación traducida automáticamente

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