Cover Image for Largest subset whose all elements are Fibonacci numbers in C++
71 views

Largest subset whose all elements are Fibonacci numbers in C++

To find the largest subset of elements in a given array where all elements are Fibonacci numbers, you can use the following C++ code. This code first generates Fibonacci numbers up to a certain limit and then checks each element in the input array to determine if it’s a Fibonacci number. Finally, it finds the largest subset of Fibonacci numbers.

C++
#include <iostream>
#include <vector>
#include <unordered_set>

// Function to generate Fibonacci numbers up to a given limit
std::vector<int> generateFibonacci(int limit) {
    std::vector<int> fibonacci;
    int a = 0, b = 1, c = 0;
    while (c <= limit) {
        fibonacci.push_back(c);
        a = b;
        b = c;
        c = a + b;
    }
    return fibonacci;
}

// Function to find the largest subset of Fibonacci numbers in an array
std::vector<int> largestFibonacciSubset(const std::vector<int>& arr) {
    // Generate Fibonacci numbers up to the maximum element in the array
    int max_element = *std::max_element(arr.begin(), arr.end());
    std::vector<int> fibonacci = generateFibonacci(max_element);

    // Create a set for faster lookup
    std::unordered_set<int> fibonacci_set(fibonacci.begin(), fibonacci.end());

    std::vector<int> result;
    for (int num : arr) {
        if (fibonacci_set.count(num)) {
            result.push_back(num);
        }
    }

    return result;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

    std::vector<int> fibonacciSubset = largestFibonacciSubset(arr);

    std::cout << "Largest Fibonacci Subset: ";
    for (int num : fibonacciSubset) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

In this code:

  1. The generateFibonacci function generates Fibonacci numbers up to a given limit and stores them in a vector.
  2. The largestFibonacciSubset function finds the largest subset of Fibonacci numbers in the input array by iterating through the array and checking if each element is in the set of generated Fibonacci numbers.
  3. The main function demonstrates how to use these functions with an example input array. You can replace the arr vector with your own input data.

Compile and run the code to find the largest subset of Fibonacci numbers in your array.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS