Найдите самую длинную подпоследовательность массива, имеющую НОК не более K

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

Дан массив arr [] из N элементов и положительное целое число K. Задача состоит в том, чтобы найти самую длинную подпоследовательность в массиве, имеющую LCM (наименьшее общее кратное) не более K. Выведите НОК и длину подпоследовательности, следуя индексам (начиная с 0) элементов полученной подпоследовательности. Выведите -1, если это невозможно.

Примеры:

Input: arr[] = {2, 3, 4, 5}, K = 14
Output:
LCM = 12, Length = 3
Indexes = 0 1 2

Input: arr[] = {12, 33, 14, 52}, K = 4
Output: -1

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

Подход: Найдите все уникальные элементы массива и их соответствующие частоты. Теперь максимальное значение LCM, которое вы должны получить, - K. Предположим, у вас есть число X такое, что 1 ≤ X ≤ K , получите все уникальные числа из массива, которым X кратно, и добавьте их частоты к numCount из X. Ответом будет число с наибольшим numCount , пусть это будет ваш LCM. Теперь, чтобы получить индексы номеров подпоследовательности, начните обход массива с начала и выведите индекс i, если LCM% arr [i] = 0 .

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the longest subsequence
// having LCM less than or equal to K
void findSubsequence(int* arr, int n, int k)
{
  
    // Map to store unique elements
    // and their frequencies
    map<int, int> M;
  
    // Update the frequencies
    for (int i = 0; i < n; ++i)
        ++M[arr[i]];
  
    // Array to store the count of numbers whom
    // 1 <= X <= K is a multiple of
    int* numCount = new int[k + 1];
  
    for (int i = 0; i <= k; ++i)
        numCount[i] = 0;
  
    // Check every unique element
    for (auto p : M) {
        if (p.first <= k) {
  
            // Find all its multiples <= K
            for (int i = 1;; ++i) {
                if (p.first * i > k)
                    break;
  
                // Store its frequency
                numCount[p.first * i] += p.second;
            }
        }
        else
            break;
    }
  
    int lcm = 0, length = 0;
  
    // Obtain the number having maximum count
    for (int i = 1; i <= k; ++i) {
        if (numCount[i] > length) {
            length = numCount[i];
            lcm = i;
        }
    }
  
    // Condition to check if answer
    // doesn"t exist
    if (lcm == 0)
        cout << -1 << endl;
    else {
  
        // Print the answer
        cout << "LCM = " << lcm
             << ", Length = " << length << endl;
  
        cout << "Indexes = ";
        for (int i = 0; i < n; ++i)
            if (lcm % arr[i] == 0)
                cout << i << " ";
    }
}
  
// Driver code
int main()
{
  
    int k = 14;
    int arr[] = { 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    findSubsequence(arr, n, k);
  
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
  
class GFG
{
    // Function to find the longest subsequence
    // having LCM less than or equal to K
    static void findSubsequence(int []arr, int n, int k)
    {
      
        // Map to store unique elements
        // and their frequencies
        HashMap<Integer, Integer> M = new HashMap<Integer,Integer>();
      
        // Update the frequencies
        for (int i = 0; i < n; ++i)
        {
            if(M.containsKey(arr[i]))
                M.put(arr[i], M.get(arr[i])+1);
            else
                M.put(arr[i], 1);
        }
          
        // Array to store the count of numbers whom
        // 1 <= X <= K is a multiple of
        int [] numCount = new int[k + 1];
      
        for (int i = 0; i <= k; ++i)
            numCount[i] = 0;
      
        Iterator<HashMap.Entry<Integer, Integer>> itr = M.entrySet().iterator(); 
          
        // Check every unique element
        while(itr.hasNext()) 
        {
            HashMap.Entry<Integer, Integer> entry = itr.next();
            if (entry.getKey() <= k) 
            {
      
                // Find all its multiples <= K
                for (int i = 1;; ++i) 
                {
                    if (entry.getKey() * i > k)
                        break;
      
                    // Store its frequency
                    numCount[entry.getKey() * i] += entry.getValue();
                }
            }
            else
                break;
        }
      
        int lcm = 0, length = 0;
      
        // Obtain the number having maximum count
        for (int i = 1; i <= k; ++i) 
        {
            if (numCount[i] > length) 
            {
                length = numCount[i];
                lcm = i;
            }
        }
      
        // Condition to check if answer
        // doesn"t exist
        if (lcm == 0)
            System.out.println(-1);
        else
        {
      
            // Print the answer
            System.out.println("LCM = " + lcm
                + " Length = " + length );
      
            System.out.print( "Indexes = ");
            for (int i = 0; i < n; ++i)
                if (lcm % arr[i] == 0)
                    System.out.print(i + " ");
        }
    }
      
    // Driver code
    public static void main (String[] args) 
    {
      
        int k = 14;
        int arr[] = { 2, 3, 4, 5 };
        int n = arr.length;
      
        findSubsequence(arr, n, k);
    }
}
  
// This code is contributed by ihritik

Python3

# Python3 implementation of the approach
from collections import defaultdict
  
# Function to find the longest subsequence
# having LCM less than or equal to K
def findSubsequence(arr, n, k):
  
    # Map to store unique elements
    # and their frequencies
    M = defaultdict(lambda:0)
  
    # Update the frequencies
    for i in range(0, n):
        M[arr[i]] += 1
  
    # Array to store the count of numbers
    # whom 1 <= X <= K is a multiple of
    numCount = [0] * (k + 1)
  
    # Check every unique element
    for p in M: 
        if p <= k: 
  
            # Find all its multiples <= K
            i = 1
            while p * i <= k: 
                  
                # Store its frequency
                numCount[p * i] += M[p]
                i += 1
          
        else:
            break
      
    lcm, length = 0, 0
  
    # Obtain the number having maximum count
    for i in range(1, k + 1): 
        if numCount[i] > length: 
            length = numCount[i]
            lcm = i
  
    # Condition to check if answer doesn"t exist
    if lcm == 0:
        print(-1)
    else:
  
        # Print the answer
        print("LCM = {0}, Length = {1}".format(lcm, length))
  
        print("Indexes = ", end = "")
        for i in range(0, n):
            if lcm % arr[i] == 0:
                print(i, end = " ")
      
# Driver code
if __name__ == "__main__":
  
    k = 14
    arr = [2, 3, 4, 5] 
    n = len(arr)
  
    findSubsequence(arr, n, k)
  
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
  
class GFG
{
    // Function to find the longest subsequence
    // having LCM less than or equal to K
    static void findSubsequence(int []arr, int n, int k)
    {
      
        // Map to store unique elements
        // and their frequencies
        Dictionary<int, int> M = new Dictionary<int, int>();
      
        // Update the frequencies
        for (int i = 0; i < n; ++i)
        {
            if(M.ContainsKey(arr[i]))
                M[arr[i]]++;
            else
                M[arr[i]] = 1;
        }
          
        // Array to store the count of numbers whom
        // 1 <= X <= K is a multiple of
        int [] numCount = new int[k + 1];
      
        for (int i = 0; i <= k; ++i)
            numCount[i] = 0;
      
        Dictionary<int, int>.KeyCollection keyColl = M.Keys;
          
        // Check every unique element
        foreach(int key in keyColl)
        {
            if ( key <= k) 
            {
      
                // Find all its multiples <= K
                for (int i = 1;; ++i) 
                {
                    if (key * i > k)
                        break;
      
                    // Store its frequency
                    numCount[key * i] += M[key];
                }
            }
            else
                break;
        }
      
        int lcm = 0, length = 0;
      
        // Obtain the number having maximum count
        for (int i = 1; i <= k; ++i)
        {
            if (numCount[i] > length) 
            {
                length = numCount[i];
                lcm = i;
            }
        }
      
        // Condition to check if answer
        // doesn"t exist
        if (lcm == 0)
            Console.WriteLine(-1);
        else 
        {
      
            // Print the answer
            Console.WriteLine("LCM = " + lcm
                + " Length = " + length );
      
            Console.Write( "Indexes = ");
            for (int i = 0; i < n; ++i)
                if (lcm % arr[i] == 0)
                    Console.Write(i + " ");
        }
    }
      
    // Driver code
    public static
C++ Алгоритмы

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

С++ Std против Stl
20 Февраля, 2023
C++ функция __builtin_popcount()
20 Февраля, 2023
Как получить доступ к элементам в наборе по индексу в С++?
20 Февраля, 2023
Строка С++ для плавающей/двойной и наоборот
20 Февраля, 2023
Преобразование шестнадцатеричной строки в целое число со знаком в С++
20 Февраля, 2023
C++ функция getenv()
20 Февраля, 2023
Вложенный, если в C++
20 Февраля, 2023
C++ вектор структур
20 Февраля, 2023