Dada una array arr[] que contiene enteros no negativos de longitud N , la tarea es imprimir la longitud de la subsecuencia más larga de números poderosos en la array.
Un número n se dice Número Poderoso si, para todo factor primo p de él, p 2 también lo divide.
Ejemplos:
Entrada: arr[] = { 3, 4, 11, 2, 9, 21 }
Salida: 2
Explicación:
La subsecuencia del número poderoso más largo es {4, 9} y, por lo tanto, la respuesta es 2.
Entrada: arr[] = { 6, 4, 10, 13, 9, 25 }
Salida: 3
Explicación:
La subsecuencia del número poderoso más largo es {4, 9, 25} y, por lo tanto, la respuesta es 3.
Enfoque: Para resolver el problema mencionado anteriormente, tenemos que seguir los pasos que se detallan a continuación:
- Recorra la array dada y para cada elemento de la array, verifique si es un número poderoso o no .
- Si el elemento es un número poderoso, estará en la subsecuencia del número poderoso más largo.
- Por lo tanto, incremente la longitud requerida de la subsecuencia del número poderoso más largo en 1
- Devuelve la longitud final después de alcanzar el tamaño de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of
// Longest Powerful Subsequence in an Array
#include <bits/stdc++.h>
using namespace std;
// Function to check if the number is powerful
bool isPowerful(int n)
{
// First divide the number repeatedly by 2
while (n % 2 == 0) {
int power = 0;
while (n % 2 == 0) {
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
// repeat above process
for (int factor = 3;
factor <= sqrt(n);
factor += 2) {
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0) {
n = n / factor;
power++;
}
// If only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers
// are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Function to find the longest subsequence
// which contain all powerful numbers
int longestPowerfulSubsequence(
int arr[], int n)
{
int answer = 0;
for (int i = 0; i < n; i++) {
if (isPowerful(arr[i]))
answer++;
}
return answer;
}
// Driver code
int main()
{
int arr[] = { 6, 4, 10, 13, 9, 25 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << longestPowerfulSubsequence(arr, n)
<< endl;
return 0;
}
Java
// Java program to find the length of
// Longest Powerful Subsequence in an Array
class GFG{
// Function to check if the number is powerful
static boolean isPowerful(int n)
{
// First divide the number repeatedly by 2
while (n % 2 == 0)
{
int power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
// repeat above process
for(int factor = 3;
factor <= Math.sqrt(n);
factor += 2)
{
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// If only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers
// are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Function to find the longest subsequence
// which contain all powerful numbers
static int longestPowerfulSubsequence(int arr[],
int n)
{
int answer = 0;
for(int i = 0; i < n; i++)
{
if (isPowerful(arr[i]))
answer++;
}
return answer;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 4, 10, 13, 9, 25 };
int n = arr.length;
System.out.print(longestPowerfulSubsequence(arr,
n) + "\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the length of # Longest Powerful Subsequence in an Array import math # Function to check if the number is powerful def isPowerful(n): # First divide the number repeatedly by 2 while (n % 2 == 0): power = 0 while (n % 2 == 0): n //= 2 power += 1 # Check if only 2^1 divides n, # then return false if (power == 1): return False # Check if n is not a power of 2 # then this loop will execute # repeat above process for factor in range(3, int(math.sqrt(n)) + 1, 2): # Find highest power of "factor" # that divides n power = 0 while (n % factor == 0): n = n // factor power += 1 # If only factor^1 divides n, # then return false if (power == 1): return False # n must be 1 now # if it is not a prime number. # Since prime numbers # are not powerful, we return # false if n is not 1. return (n == 1) # Function to find the longest subsequence # which contain all powerful numbers def longestPowerfulSubsequence(arr, n): answer = 0 for i in range(n): if (isPowerful(arr[i])): answer += 1 return answer # Driver code arr = [ 6, 4, 10, 13, 9, 25 ] n = len(arr) print(longestPowerfulSubsequence(arr, n)) # This code is contributed by sanjoy_62
C#
// C# program to find the length of
// longest Powerful Subsequence in
// an array
using System;
class GFG{
// Function to check if the
// number is powerful
static bool isPowerful(int n)
{
// First divide the number
// repeatedly by 2
while (n % 2 == 0)
{
int power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// Check if only 2^1 divides
// n, then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
// repeat above process
for(int factor = 3;
factor <= Math.Sqrt(n);
factor += 2)
{
// Find highest power of "factor"
// that divides n
int power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// If only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers
// are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Function to find the longest subsequence
// which contain all powerful numbers
static int longestPowerfulSubsequence(int []arr,
int n)
{
int answer = 0;
for(int i = 0; i < n; i++)
{
if (isPowerful(arr[i]))
answer++;
}
return answer;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 6, 4, 10, 13, 9, 25 };
int n = arr.Length;
Console.Write(longestPowerfulSubsequence(arr,
n) + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program to find the length of
// Longest Powerful Subsequence in an Array
// Function to check if the number is powerful
function isPowerful(n)
{
// First divide the number repeatedly by 2
while (n % 2 == 0)
{
let power = 0;
while (n % 2 == 0)
{
n /= 2;
power++;
}
// Check if only 2^1 divides n,
// then return false
if (power == 1)
return false;
}
// Check if n is not a power of 2
// then this loop will execute
// repeat above process
for(let factor = 3;
factor <= Math.sqrt(n);
factor += 2)
{
// Find highest power of "factor"
// that divides n
let power = 0;
while (n % factor == 0)
{
n = n / factor;
power++;
}
// If only factor^1 divides n,
// then return false
if (power == 1)
return false;
}
// n must be 1 now
// if it is not a prime number.
// Since prime numbers
// are not powerful, we return
// false if n is not 1.
return (n == 1);
}
// Function to find the longest subsequence
// which contain all powerful numbers
function longestPowerfulSubsequence(arr,
n)
{
let answer = 0;
for(let i = 0; i < n; i++)
{
if (isPowerful(arr[i]))
answer++;
}
return answer;
}
// Driver code
let arr = [ 6, 4, 10, 13, 9, 25 ];
let n = arr.length;
document.write(longestPowerfulSubsequence(arr,
n) + "\n");
// This code is contributed by souravghosh0416.
</script>
Producción:
3
Complejidad de tiempo: O(N*√N)
Complejidad de espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA