Length of largest subarray whose all elements Powerful number
Given an array arr[] of integer elements, the task is to find the length of the largest sub-array of arr[] such that all the elements of the sub-array are Powerful number.
A number n is said to be Powerful Number if, for every prime factor p of it, p2 also divides it.
Examples:
Input: arr[] = {1, 7, 36, 4, 6, 28, 4}
Output:2
Maximum length sub-array with all elements as Powerful number is {36, 4}
Input: arr[] = {25, 100, 2, 3, 9, 1}
Output: 2
Maximum length sub-array with all elements as Powerful number is {25, 100} or {9, 1}
Approach:
- Traverse the array from left to right. Initialize a max_length and current_length variable with 0.
- If the current element is a Powerful number then increment current_length variable and continue. Otherwise, set current_length = 0.
- At each step, assign max_length as max_length = max(current_length, max_length).
- Print the value of max_length in the end.
C++
// C++ program to find the length of the // largest sub-array of an array every // element of whose is a powerful number #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++; } // If only 2^1 divides n // (not higher powers), // then return false if (power == 1) return false ; } // 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 // (not higher powers), // 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 return the length of the // largest sub-array of an array every // element of whose is a powerful number int contiguousPowerfulNumber( int arr[], int n) { int current_length = 0; int max_length = 0; for ( int i = 0; i < n; i++) { // If arr[i] is // a Powerful number if (isPowerful(arr[i])) current_length++; else current_length = 0; max_length = max(max_length, current_length); } return max_length; } // Driver code int main() { int arr[] = { 1, 7, 36, 4, 6, 28, 4 }; int n = sizeof (arr) / sizeof (arr[0]); cout << contiguousPowerfulNumber(arr, n); return 0; } |
Java
// Java program to find the length of the // largest sub-array of an array every // element of whose is a powerful number import java.util.*; class solution{ // 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++; } // If only 2^1 divides n // (not higher powers), // then return false if (power == 1 ) return false ; } // 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 // (not higher powers), // 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 return the length of the // largest sub-array of an array every // element of whose is a powerful number static int contiguousPowerfulNumber( int [] arr, int n) { int current_length = 0 ; int max_length = 0 ; for ( int i = 0 ; i < n; i++) { // If arr[i] is // a Powerful number if (isPowerful(arr[i])) current_length++; else current_length = 0 ; max_length = Math.max(max_length, current_length); } return max_length; } // Driver code public static void main(String args[]) { int []arr = { 1 , 7 , 36 , 4 , 6 , 28 , 4 }; int n = arr.length; System.out.println(contiguousPowerfulNumber(arr, n)); } } // This code is contributed by Bhupendra_Singh |
Python3
# Python 3 program to find the length of # the largest sub-array of an array every # element of whose is a powerful number 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 = n / / 2 power = power + 1 # If only 2 ^ 1 divides # n (not higher powers), # then return false if (power = = 1 ): return False # 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 = power + 1 # If only factor ^ 1 divides # n (not higher powers), # 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 return the length of the # largest sub-array of an array every # element of whose is a powerful number def contiguousPowerfulNumber(arr, n): current_length = 0 max_length = 0 for i in range ( 0 , n, 1 ): # If arr[i] is a # Powerful number if (isPowerful(arr[i])): current_length + = 1 else : current_length = 0 max_length = max (max_length, current_length) return max_length # Driver code if __name__ = = '__main__' : arr = [ 1 , 7 , 36 , 4 , 6 , 28 , 4 ] n = len (arr) print (contiguousPowerfulNumber(arr, n)) |
C#
// C# program to find the length of the // largest sub-array of an array every // element of whose is a powerful number using System; class solution{ // 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++; } // If only 2^1 divides n // (not higher powers), // then return false if (power == 1) return false ; } // 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 // (not higher powers), // 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 return the length of the // largest sub-array of an array every // element of whose is a powerful number static int contiguousPowerfulNumber( int [] arr, int n) { int current_length = 0; int max_length = 0; for ( int i = 0; i < n; i++) { // If arr[i] is // a Powerful number if (isPowerful(arr[i])) current_length++; else current_length = 0; max_length = Math.Max(max_length, current_length); } return max_length; } // Driver code public static void Main(String []args) { int []arr = { 1, 7, 36, 4, 6, 28, 4 }; int n = arr.Length; Console.WriteLine(contiguousPowerfulNumber(arr, n)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program to find the length of the // largest sub-array of an array every // element of whose is a powerful number // 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++; } // If only 2^1 divides n // (not higher powers), // then return false if (power == 1) return false ; } // 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 // (not higher powers), // 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 return the length of the // largest sub-array of an array every // element of whose is a powerful number function contiguousPowerfulNumber(arr, n) { let current_length = 0; let max_length = 0; for (let i = 0; i < n; i++) { // If arr[i] is // a Powerful number if (isPowerful(arr[i])) current_length++; else current_length = 0; max_length = Math.max(max_length, current_length); } return max_length; } // Driver Code let arr = [ 1, 7, 36, 4, 6, 28, 4 ]; let n = arr.length; document.write(contiguousPowerfulNumber(arr, n)); </script> |
Output:
2
Time Complexity: O(N×√N)
Auxiliary Space Complexity: O(1)