Recuento de números cuya diferencia con Fibonacci cuenta hasta ellos es al menos K

Posted on by Rudeus Greyrat

Requisitos previos: Búsqueda binaria
Dados dos números enteros positivos N y K , la tarea es contar todos los números que cumplan las siguientes condiciones: 
Si el número es num , 
 

  • número ≤ norte .
  • abs(num – count) ≥ K donde count es el conteo de números de Fibonacci hasta num .

Ejemplos: 
 

Entrada: N = 10, K = 3 
Salida: 2 
Explicación: 
9 y 10 son los números válidos que satisfacen las condiciones dadas. 
Para el 9, la diferencia entre el 9 y los números de Fibonacci hasta el 9 (0, 1, 2, 3, 5, 8) es, por ejemplo, 9 – 6 = 3. 
Para el 10, la diferencia entre el 9 y los números de Fibonacci hasta el 10 (0, 1, 2, 3, 5, 8) es, por ejemplo, 10 – 6 = 4.
Entrada: N = 30, K = 7 
Salida: 11 
 

Observación: Al observar detenidamente, la función que es la diferencia del número y cuenta de números de fibonacci hasta ese número es una función monótonamente creciente para un K particular . Además, si un número X es un número válido, entonces X + 1 también será un número válido.
Prueba: 
 

  • Deje que la función C i denote el recuento de números de Fibonacci hasta el número i .
  • Ahora, para el número X + 1 la diferencia es X + 1 – C X + 1 que es mayor o igual que la diferencia X – C X para el número X, es decir (X + 1 – C X + 1 ) ≥ ( X – C X ) .
  • Así, si (X – C X ) ≥ S , entonces (X + 1 – CX + 1) ≥ S .

Enfoque: por lo tanto, a partir de la observación anterior, la idea es usar hashing para precalcular y almacenar los Nodes de Fibonacci hasta el valor máximo y crear una array de prefijos utilizando el concepto de array de suma de prefijos donde cada índice almacena la cantidad de números de Fibonacci menores que ‘ i’ para que la verificación sea fácil y eficiente (en tiempo O(1)).
Ahora, podemos usar la búsqueda binaria para encontrar el número mínimo válido X , ya que todos los números en el rango [ X , N ] son ​​válidos. Por lo tanto, la respuesta sería N – X + 1 .
A continuación se muestra la implementación del enfoque anterior:
 
 

C++

// C++ program to find the count
// of numbers whose difference with
// Fibonacci count upto them is atleast K
 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1000005;
 
// fibUpto[i] denotes the count of
// fibonacci numbers upto i
int fibUpto[MAX + 1];
 
// Function to compute all the Fibonacci
// numbers and update fibUpto array
void compute(int sz)
{
    bool isFib[sz + 1];
    memset(isFib, false, sizeof(isFib));
 
    // Store the first two Fibonacci numbers
    int prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
 
    // Compute the Fibonacci numbers
    // and store them in isFib array
    while (curr <= sz) {
        int temp = curr + prev;
        isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
 
    // Compute fibUpto array
    fibUpto[0] = 1;
    for (int i = 1; i <= sz; i++) {
        fibUpto[i] = fibUpto[i - 1];
        if (isFib[i])
            fibUpto[i]++;
    }
}
 
// Function to return the count
// of valid numbers
int countOfNumbers(int N, int K)
{
 
    // Compute fibUpto array
    compute(N);
 
    // Binary search to find the minimum
    // number that follows the condition
    int low = 1, high = N, ans = 0;
    while (low <= high) {
        int mid = (low + high) >> 1;
 
        // Check if the number is
        // valid, try to reduce it
        if (mid - fibUpto[mid] >= K) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
 
    // Ans is the minimum valid number
    return (ans ? N - ans + 1 : 0);
}
 
// Driver Code
int main()
{
    int N = 10, K = 3;
 
    cout << countOfNumbers(N, K);
}

Java

// Java program to find the count
// of numbers whose difference with
// Fibonacci count upto them is atleast K
import java.util.*;
 
class GFG{
  
static int MAX = 1000005;
  
// fibUpto[i] denotes the count of
// fibonacci numbers upto i
static int []fibUpto = new int[MAX + 1];
  
// Function to compute all the Fibonacci
// numbers and update fibUpto array
static void compute(int sz)
{
    boolean []isFib = new boolean[sz + 1];
  
    // Store the first two Fibonacci numbers
    int prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
  
    // Compute the Fibonacci numbers
    // and store them in isFib array
    while (curr <= sz) {
        int temp = curr + prev;
        if(temp <= sz)
            isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
  
    // Compute fibUpto array
    fibUpto[0] = 1;
    for (int i = 1; i <= sz; i++) {
        fibUpto[i] = fibUpto[i - 1];
        if (isFib[i])
            fibUpto[i]++;
    }
}
  
// Function to return the count
// of valid numbers
static int countOfNumbers(int N, int K)
{
  
    // Compute fibUpto array
    compute(N);
  
    // Binary search to find the minimum
    // number that follows the condition
    int low = 1, high = N, ans = 0;
    while (low <= high) {
        int mid = (low + high) >> 1;
  
        // Check if the number is
        // valid, try to reduce it
        if (mid - fibUpto[mid] >= K) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
  
    // Ans is the minimum valid number
    return (ans>0 ? N - ans + 1 : 0);
}
  
// Driver Code
public static void main(String[] args)
{
    int N = 10, K = 3;
  
    System.out.print(countOfNumbers(N, K));
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python 3 program to find the count
# of numbers whose difference with
# Fibonacci count upto them is atleast K
 
MAX = 1000005
 
# fibUpto[i] denotes the count of
# fibonacci numbers upto i
fibUpto = [0]*(MAX + 1)
 
# Function to compute all the Fibonacci
# numbers and update fibUpto array
def compute(sz):
 
    isFib = [False]*(sz + 1)
    # Store the first two Fibonacci numbers
    prev = 0
    curr = 1
    isFib[prev] = True
    isFib[curr] = True
 
    # Compute the Fibonacci numbers
    # and store them in isFib array
    while (curr <=sz):
        temp = curr + prev
        if(temp<=sz):
            isFib[temp] = True
        prev = curr
        curr = temp
 
    # Compute fibUpto array
    fibUpto[0] = 1
    for i in range( 1,sz+1):
        fibUpto[i] = fibUpto[i - 1]
        if (isFib[i]):
            fibUpto[i]+=1
 
# Function to return the count
# of valid numbers
def countOfNumbers(N, K):
 
    # Compute fibUpto array
    compute(N)
 
    # Binary search to find the minimum
    # number that follows the condition
    low , high, ans = 1, N, 0
    while (low <= high):
        mid = (low + high) >> 1
 
        # Check if the number is
        # valid, try to reduce it
        if (mid - fibUpto[mid] >= K):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
 
    # Ans is the minimum valid number
    if(ans):
        return (N - ans + 1)
    return 0
     
# Driver Code
if __name__ == "__main__":
     
    N = 10
    K = 3
 
    print(countOfNumbers(N, K))
 
# This code is contributed by chitranayal

C#

// C# program to find the count
// of numbers whose difference with
// Fibonacci count upto them is atleast K
using System;
  
class GFG{
   
static int MAX = 1000005;
   
// fibUpto[i] denotes the count of
// fibonacci numbers upto i
static int []fibUpto = new int[MAX + 1];
   
// Function to compute all the Fibonacci
// numbers and update fibUpto array
static void compute(int sz)
{
    bool []isFib = new bool[sz + 1];
   
    // Store the first two Fibonacci numbers
    int prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
   
    // Compute the Fibonacci numbers
    // and store them in isFib array
    while (curr <= sz) {
        int temp = curr + prev;
        if(temp <= sz)
            isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
   
    // Compute fibUpto array
    fibUpto[0] = 1;
    for (int i = 1; i <= sz; i++) {
        fibUpto[i] = fibUpto[i - 1];
        if (isFib[i])
            fibUpto[i]++;
    }
}
   
// Function to return the count
// of valid numbers
static int countOfNumbers(int N, int K)
{
   
    // Compute fibUpto array
    compute(N);
   
    // Binary search to find the minimum
    // number that follows the condition
    int low = 1, high = N, ans = 0;
    while (low <= high) {
        int mid = (low + high) >> 1;
   
        // Check if the number is
        // valid, try to reduce it
        if (mid - fibUpto[mid] >= K) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
   
    // Ans is the minimum valid number
    return (ans>0 ? N - ans + 1 : 0);
}
   
// Driver Code
public static void Main()
{
    int N = 10, K = 3;
   
    Console.WriteLine(countOfNumbers(N, K));
}
}
  
// This code is contributed by Mohitkumar29

Javascript

<script>
// Javascript program to find the count
// of numbers whose difference with
// Fibonacci count upto them is atleast K
let MAX = 1000005;
 
// fibUpto[i] denotes the count of
// fibonacci numbers upto i
let fibUpto = new Array(MAX+1);
 
// Function to compute all the Fibonacci
// numbers and update fibUpto array
function compute(sz)
{
    let isFib = new Array(sz + 1);
    
    // Store the first two Fibonacci numbers
    let prev = 0, curr = 1;
    isFib[prev] = isFib[curr] = true;
    
    // Compute the Fibonacci numbers
    // and store them in isFib array
    while (curr <= sz) {
        let temp = curr + prev;
        if(temp <= sz)
            isFib[temp] = true;
        prev = curr;
        curr = temp;
    }
    
    // Compute fibUpto array
    fibUpto[0] = 1;
    for (let i = 1; i <= sz; i++) {
        fibUpto[i] = fibUpto[i - 1];
        if (isFib[i])
            fibUpto[i]++;
    }
}
 
// Function to return the count
// of valid numbers
function countOfNumbers(N,K)
{
    // Compute fibUpto array
    compute(N);
    
    // Binary search to find the minimum
    // number that follows the condition
    let low = 1, high = N, ans = 0;
    while (low <= high) {
        let mid = (low + high) >> 1;
    
        // Check if the number is
        // valid, try to reduce it
        if (mid - fibUpto[mid] >= K) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    
    // Ans is the minimum valid number
    return (ans>0 ? N - ans + 1 : 0);
}
 
// Driver Code
let N = 10, K = 3;
document.write(countOfNumbers(N, K));
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

2

 

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 *