Самая длинная подпоследовательность массива, содержащего числа Люка

Опубликовано: 14 Января, 2022

Для массива arr [] из N элементов задача состоит в том, чтобы найти длину самой длинной подпоследовательности в arr [] , чтобы все элементы последовательности были числами Люка.
Примеры:

Input: arr[] = {2, 3, 55, 6, 1, 18} 
Output: 4 
1, 2, 3 and 18 are the only elements from the Lucas sequence.
Input: arr[] = {22, 33, 2, 123} 
Output: 2 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

  • Найдите максимальный элемент в массиве.
  • Сгенерируйте числа Лукаса до максимума и сохраните их в наборе.
  • Пройдите по массиву arr [] и проверьте, присутствует ли текущий элемент в наборе.
  • Если он присутствует в наборе, увеличьте счетчик.

Below is the implementation of the above approach: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the length of
// the longest required sub-sequence
int LucasSequence(int arr[], int n)
{
    // Find the maximum element from
    // the array
    int max = *max_element(arr, arr+n);
 
    // Insert all lucas numbers
    // below max to the set
    // a and b are first two elements
    // of the Lucas sequence
    unordered_set<int> s;
    int a = 2, b = 1, c;
    s.insert(a);
    s.insert(b);
    while (b < max) {
        int c = a + b;
        a = b;
        b = c;
        s.insert(b);
    }
 
    int count = 0;
    for (int i = 0; i < n; i++) {
 
        // If current element is a Lucas
        // number, increment count
        auto it = s.find(arr[i]);
        if (it != s.end())
            count++;
    }
 
    // Return the count
    return count;
}
 
// Driver code
int main()
{
    int arr[] = { 7, 11, 22, 4, 2, 1, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << LucasSequence(arr, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Function to return the length of
    // the longest required sub-sequence
    static int LucasSequence(int[] arr, int n)
    {
        // Find the maximum element from
        // the array
        int max = Arrays.stream(arr).max().getAsInt();
        int counter = 0;
 
        // Insert all lucas numbers
        // below max to the set
        // a and b are first two elements
        // of the Lucas sequence
        HashSet<Integer> s = new HashSet<>();
 
        int a = 2, b = 1;
        s.add(a);
        s.add(b);
 
        while (b < max)
        {
            int c = a + b;
            a = b;
            b = c;
            s.add(b);
        }
 
        for (int i = 0; i < n; i++)
        {
 
            // If current element is a Lucas
            // number, increment count
            if (s.contains(arr[i]))
            {
                counter++;
            }
        }
 
        // Return the count
        return counter;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = {7, 11, 22, 4, 2, 1, 8, 9};
        int n = arr.length;
 
        System.out.println(LucasSequence(arr, n));
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python 3 implementation of the approach
 
# Function to return the length of
# the longest required sub-sequence
def LucasSequence(arr, n):
     
    # Find the maximum element from
    # the array
    max = arr[0]
    for i in range(len(arr)):
        if(arr[i] > max):
            max = arr[i]
 
    # Insert all lucas numbers below max
    # to the set a and b are first two
    # elements of the Lucas sequence
    s = set()
    a = 2
    b = 1
    s.add(a)
    s.add(b)
    while (b < max):
        c = a + b
        a = b
        b = c
        s.add(b)
 
    count = 0
    for i in range(n):
         
        # If current element is a Lucas
        # number, increment count
        if(arr[i] in s):
            count += 1
 
    # Return the count
    return count
 
# Driver code
if __name__ == "__main__":
    arr = [7, 11, 22, 4, 2, 1, 8, 9]
    n = len(arr)
 
    print(LucasSequence(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG
{
     
    // Function to return the length of
    // the longest required sub-sequence
    static int LucasSequence(int []arr, int n)
    {
        // Find the maximum element from
        // the array
        int max = arr.Max();
        int counter = 0;
 
        // Insert all lucas numbers
        // below max to the set
        // a and b are first two elements
        // of the Lucas sequence
        HashSet<int> s = new HashSet<int>() ;
         
        int a = 2, b = 1 ;
        s.Add(a);
        s.Add(b);
         
        while (b < max)
        {
            int c = a + b;
            a = b;
            b = c;
            s.Add(b);
        }
     
        for (int i = 0; i < n; i++)
        {
     
            // If current element is a Lucas
            // number, increment count
            if (s.Contains(arr[i]))
                counter++;
        }
     
        // Return the count
        return counter;
    }
 
    // Driver code
    static public void Main()
    {
        int []arr = { 7, 11, 22, 4, 2, 1, 8, 9 };
        int n = arr.Length ;
     
        Console.WriteLine(LucasSequence(arr, n)) ;
    }
}
 
// This code is contributed by Ryuga

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the length of
// the longest required sub-sequence
function LucasSequence(arr, n)
{
    // Find the maximum element from
    // the array
    var max = arr.reduce((a,b)=> Math.max(a,b));
 
    // push all lucas numbers
    // below max to the set
    // a and b are first two elements
    // of the Lucas sequence
    var s = [];
    var a = 2, b = 1, c;
    s.push(a);
    s.push(b);
    while (b < max) {
        var c = a + b;
        a = b;
        b = c;
        s.push(b);
    }
 
    s.sort((a,b) => a-b)
    var count = 0;
    for (var i = 0; i < n; i++) {
 
        // If current element is a Lucas
        // number, increment count
        if(s.includes(arr[i]))
        {
            s.pop(arr[i]);
            count++;
        }
    }
 
    // Return the count
    return count;
}
 
// Driver code
var arr = [7, 11, 22, 4, 2, 1, 8, 9 ];
var n = arr.length;
document.write( LucasSequence(arr, n));
 
</script>
Output: 
5

 

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ