Dada una array arr[] de N elementos y un entero positivo K . La tarea es encontrar la subsecuencia más larga en la array que tenga LCM (Mínimo común múltiplo) como máximo K . Imprime el LCM y la longitud de la subsecuencia, siguiendo los índices (a partir de 0) de los elementos de la subsecuencia obtenida. Imprime -1 si no es posible hacerlo.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 5}, K = 14
Salida:
LCM = 12, Longitud = 3
Índices = 0 1 2
Entrada: arr[] = {12, 33, 14, 52}, K = 4
Salida: -1
Enfoque: Encuentre todos los elementos únicos de la array y sus respectivas frecuencias. Ahora, el MCM más alto que se supone que debes obtener es K . Suponga que tiene un número X tal que 1 ≤ X ≤ K , obtenga todos los números únicos de la array de los que X es un múltiplo y agregue sus frecuencias a numCount de X . La respuesta será el número con el numCount más alto , que sea su LCM. Ahora, para obtener los índices de los números de la subsecuencia, comience a recorrer la array desde el principio e imprima el índice i si LCM % arr[i] = 0 .
A continuación se muestra la implementación del enfoque anterior:
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 void Main ()
{
int k = 14;
int []arr = { 2, 3, 4, 5 };
int n = arr.Length;
findSubsequence(arr, n, k);
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the approach
// Function to find the longest subsequence
// having LCM less than or equal to K
function findSubsequence($arr, $n, $k)
{
// Map to store unique elements
// and their frequencies
$M = array();
for($i = 0; $i < $n; $i++)
$M[$arr[$i]] = 0 ;
// Update the frequencies
for ($i = 0; $i < $n; ++$i)
++$M[$arr[$i]];
// Array to store the count of numbers
// whom 1 <= X <= K is a multiple of
$numCount = array();
for ($i = 0; $i <= $k; ++$i)
$numCount[$i] = 0;
// Check every unique element
foreach($M as $key => $value)
{
if ($key <= $k)
{
// Find all its multiples <= K
for ($i = 1;; ++$i)
{
if ($key * $i > $k)
break;
// Store its frequency
$numCount[$key * $i] += $value;
}
}
else
break;
}
$lcm = 0; $length = 0;
// Obtain the number having
// maximum count
for ($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)
echo -1 << "\n";
else
{
// Print the answer
echo "LCM = ", $lcm,
", Length = ", $length, "\n";
echo "Indexes = ";
for ($i = 0; $i < $n; ++$i)
if ($lcm % $arr[$i] == 0)
echo $i, " ";
}
}
// Driver code
$k = 14;
$arr = array( 2, 3, 4, 5 );
$n = count($arr);
findSubsequence($arr, $n, $k);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to find the longest subsequence
// having LCM less than or equal to K
function findSubsequence(arr, n, k) {
// Map to store unique elements
// and their frequencies
let M = new Map();
// Update the frequencies
for (let i = 0; i < n; ++i) {
if (M.has(arr[i])) {
M.set(arr[i], M.get(arr[i]) + 1)
} else {
M.set(arr[i], 1)
}
}
// Array to store the count of numbers whom
// 1 <= X <= K is a multiple of
let numCount = new Array(k + 1);
for (let i = 0; i <= k; ++i)
numCount[i] = 0;
// Check every unique element
for (let p of M) {
if (p[0] <= k) {
// Find all its multiples <= K
for (let i = 1; ; ++i) {
if (p[0] * i > k)
break;
// Store its frequency
numCount[p[0] * i] += p[1];
}
}
else
break;
}
let lcm = 0, length = 0;
// Obtain the number having maximum count
for (let 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)
document.write(-1 + "<br>");
else {
// Print the answer
document.write(
"LCM = " + lcm + ", Length = " + length + "<br>"
);
document.write("Indexes = ");
for (let i = 0; i < n; ++i)
if (lcm % arr[i] == 0)
document.write(i + " ");
}
}
// Driver code
let k = 14;
let arr = [2, 3, 4, 5];
let n = arr.length;
findSubsequence(arr, n, k);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
LCM = 12, Length = 3 Indexes = 0 1 2
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por NaimishSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA