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