Given an array arr[] containing non-negative integers of length N, the task is to print the length of the longest subsequence of Powerful numbers in the array.
A number n is said to be Powerful Number if, for every prime factor p of it, p2 also divides it.
Examples:
Input: arr[] = { 3, 4, 11, 2, 9, 21 }
Output: 2
Explanation:
Longest Powerful number Subsequence is {4, 9} and hence the answer is 2.
Input: arr[] = { 6, 4, 10, 13, 9, 25 }
Output: 3
Explanation:
Longest Powerful number Subsequence is {4, 9, 25} and hence the answer is 3.
Approach: To solve the problem mentioned above, we have to follow the steps given below:
- Traverse the given array and for each element in the array, check if it is Powerful number or not.
- If the element is a Powerful number, it will be in Longest Powerful number Subsequence.
- Hence increment the required length of Longest Powerful number Subsequence by 1
- Return the final length after reaching the size of the array.
Below is the implementation of the above approach:
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> |
3
Time Complexity: O(N*?N)
Auxiliary Space Complexity: O(1)