Given an array arr[] consisting of N positive integers, the task is to find the length of the longest subarray having a product of elements of that subarray equal to a perfect power of 2.
Examples:
Input: arr[] = {2, 5, 4, 4, 6}
Output: 2
Explanation:
The subarray having maximum length whose product is perfect power of 2 is {4, 4}.
Product = 4 * 4 = 16, which is a perfect power of 2.Input: arr[] = {2, 5, 4, 6, 8, 8, 2}
Output: 3
Explanation:
The subarray having maximum length whose product is perfect power of 2 is {8, 8, 2}.
Product = 8 * 8 * 2 = 128, which is a perfect power of 2.
Naive Approach: The simplest approach is to generate all possible subarrays of the given array and check if the product of the elements of any subarray is a perfect power of 2 or not. If found to be true, then update the maximum length to the length of this subarray. Finally, print the maximum length of the subarray obtained after checking all possible subarray.
Below is the code for above approach :
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether a number // is power of 2 or not bool isPower( int x) { return (x && (!(x & (x - 1)))); } // Function to find maximum length // subarray having product of element // as a perfect power of 2 int maximumlength( int arr[], int N) { // Stores maximum subarray length int max_len_subarray = 0; // Traverse the given array for ( int i = 0; i < N; i++) { int prod = 1; // Consider all subarrays starting from i for ( int j = i; j < N; j++) { prod *= arr[j]; if (isPower(prod)) { max_len_subarray = max(max_len_subarray, j - i + 1); } } } // Print the maximum length cout << max_len_subarray; } // Driver Code int main() { // Given arr[] int arr[] = { 2, 5, 4, 6, 8, 8, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call maximumlength(arr, N); return 0; } |
Java
import java.util.*; public class GFG { // Function to check whether a number // is power of 2 or not public static boolean isPower( int x) { return (x != 0 ) && ((x & (x - 1 )) == 0 ); } // Function to find maximum length // subarray having product of element // as a perfect power of 2 public static int maximumLength( int [] arr) { int N = arr.length; int max_len_subarray = 0 ; // Traverse the given array for ( int i = 0 ; i < N; i++) { int prod = 1 ; // Consider all subarrays starting from i for ( int j = i; j < N; j++) { prod *= arr[j]; if (isPower(prod)) { max_len_subarray = Math.max(max_len_subarray, j - i + 1 ); } } } // Return the maximum length return max_len_subarray; } // Driver Code public static void main(String[] args) { // Given arr[] int [] arr = { 2 , 5 , 4 , 6 , 8 , 8 , 2 }; // Function Call int maxLength = maximumLength(arr); // Print the maximum length System.out.println(maxLength); } } |
Python3
# Python3 code def is_power(x): return x ! = 0 and (x & (x - 1 )) = = 0 def maximum_length(arr, N): max_len_subarray = 0 for i in range (N): prod = 1 for j in range (i, N): prod * = arr[j] if is_power(prod): max_len_subarray = max (max_len_subarray, j - i + 1 ) return max_len_subarray # Driver Code if __name__ = = "__main__" : # Given arr[] arr = [ 2 , 5 , 4 , 6 , 8 , 8 , 2 ] N = len (arr) # Function Call max_length = maximum_length(arr, N) # Print the maximum length print (max_length) |
C#
using System; class Program { // Function to check whether a number // is a power of 2 or not static bool IsPower( int x) { return (x != 0) && ((x & (x - 1)) == 0); } // Function to find the maximum length // subarray having a product of elements // as a perfect power of 2 static int MaximumLength( int [] arr) { int n = arr.Length; int maxLenSubarray = 0; // Traverse the given array for ( int i = 0; i < n; i++) { int prod = 1; // Consider all subarrays starting from i for ( int j = i; j < n; j++) { prod *= arr[j]; if (IsPower(prod)) { maxLenSubarray = Math.Max(maxLenSubarray, j - i + 1); } } } return maxLenSubarray; } // Driver Code static void Main( string [] args) { // Given arr[] int [] arr = { 2, 5, 4, 6, 8, 8, 2 }; // Function Call int result = MaximumLength(arr); Console.WriteLine(result); } } |
Javascript
// Function to check whether a number is a power of 2 or not function isPower(x) { return (x !== 0) && ((x & (x - 1)) === 0); } // Function to find the maximum length subarray having a product of elements as a perfect power of 2 function maximumLength(arr) { const n = arr.length; let maxLenSubarray = 0; // Traverse the given array for (let i = 0; i < n; i++) { let prod = 1; // Consider all subarrays starting from i for (let j = i; j < n; j++) { prod *= arr[j]; if (isPower(prod)) { maxLenSubarray = Math.max(maxLenSubarray, j - i + 1); } } } return maxLenSubarray; } // Driver Code const arr = [2, 5, 4, 6, 8, 8, 2]; // Function Call const result = maximumLength(arr); console.log(result); |
3
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based upon the fact that for any number to be a power of 2 it can be also be expressed as the product of numbers having perfect power of 2. Therefore, the idea is to use the Kadane’s Algorithm to find the maximum length of the subarray having all elements having perfect power of 2. Below are the steps:
- Initialize maxLength and ans as 0 that will store the maximum length of subarrays and a resultant maximum length of subarray respectively.
- Traverse the given array and do the following:
- If the current element is a perfect power of 2 then increment the maxLength by 1. Else update maxLength as 0.
- Update ans to the maximum of ans and maxLength after the above step.
- Print the value of ans as the maximum length after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether a number // is power of 2 or not bool isPower( int x) { return (x && (!(x & (x - 1)))); } // Function to find maximum length // subarray having product of element // as a perfect power of 2 int maximumlength( int arr[], int N) { // Stores current subarray length int max_length = 0; // Stores maximum subarray length int max_len_subarray = 0; // Traverse the given array for ( int i = 0; i < N; i++) { // If arr[i] is power of 2 if (isPower(arr[i]) == 1) { // Increment max_length max_length++; // Update max_len_subarray max_len_subarray = max(max_length, max_len_subarray); } // Otherwise else { max_length = 0; } } // Print the maximum length cout << max_len_subarray; } // Driver Code int main() { // Given arr[] int arr[] = { 2, 5, 4, 6, 8, 8, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call maximumlength(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check whether a number // is power of 2 or not public static boolean isPower( int x) { if (x != 0 && (x & (x - 1 )) == 0 ) return true ; return false ; } // Function to find maximum length // subarray having product of element // as a perfect power of 2 public static void maximumlength( int arr[], int N) { // Stores current subarray length int max_length = 0 ; // Stores maximum subarray length int max_len_subarray = 0 ; // Traverse the given array for ( int i = 0 ; i < N; i++) { // If arr[i] is power of 2 if (isPower(arr[i])) { // Increment max_length max_length++; // Update max_len_subarray max_len_subarray = Math.max(max_length, max_len_subarray); } // Otherwise else { max_length = 0 ; } } // Print the maximum length System.out.println(max_len_subarray); } // Driver Code public static void main(String args[]) { // Given arr[] int arr[] = { 2 , 5 , 4 , 6 , 8 , 8 , 2 }; int N = arr.length; // Function Call maximumlength(arr, N); } } // This code is contributed by hemanthswarna1506 |
Python3
# Python3 program for the # above approach # Function to check whether # a number is power of 2 # or not def isPower(x): if (x ! = 0 and (x & (x - 1 )) = = 0 ): return True ; return False ; # Function to find maximum # length subarray having # product of element # as a perfect power of 2 def maximumlength(arr, N): # Stores current # subarray length max_length = 0 ; # Stores maximum # subarray length max_len_subarray = 0 ; # Traverse the given array for i in range (N): # If arr[i] is power of 2 if (isPower(arr[i])): # Increment max_length max_length + = 1 ; # Update max_len_subarray max_len_subarray = max (max_length, max_len_subarray); # Otherwise else : max_length = 0 ; # Print maximum length print (max_len_subarray); # Driver Code if __name__ = = '__main__' : # Given arr arr = [ 2 , 5 , 4 , 6 , 8 , 8 , 2 ]; N = len (arr); # Function Call maximumlength(arr, N); # This code is contributed by gauravrajput1 |
C#
// C# program for the above approach using System; class GFG{ // Function to check whether a number // is power of 2 or not public static bool isPower( int x) { if (x != 0 && (x & (x - 1)) == 0) return true ; return false ; } // Function to find maximum length // subarray having product of element // as a perfect power of 2 public static void maximumlength( int [] arr, int N) { // Stores current subarray length int max_length = 0; // Stores maximum subarray length int max_len_subarray = 0; // Traverse the given array for ( int i = 0; i < N; i++) { // If arr[i] is power of 2 if (isPower(arr[i])) { // Increment max_length max_length++; // Update max_len_subarray max_len_subarray = Math.Max(max_length, max_len_subarray); } // Otherwise else { max_length = 0; } } // Print the maximum length Console.WriteLine(max_len_subarray); } // Driver Code public static void Main() { // Given arr[] int [] arr = { 2, 5, 4, 6, 8, 8, 2 }; int N = arr.Length; // Function Call maximumlength(arr, N); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // JavaScript program for the above approach // Function to check whether a number // is power of 2 or not function isPower(x) { return (x && (!(x & (x - 1)))); } // Function to find maximum length // subarray having product of element // as a perfect power of 2 function maximumlength(arr, N) { // Stores current subarray length var max_length = 0; // Stores maximum subarray length var max_len_subarray = 0; // Traverse the given array for ( var i = 0; i < N; i++) { // If arr[i] is power of 2 if (isPower(arr[i]) == 1) { // Increment max_length max_length++; // Update max_len_subarray max_len_subarray = Math.max(max_length, max_len_subarray); } // Otherwise else { max_length = 0; } } // Print the maximum length document.write( max_len_subarray); } // Driver Code // Given arr[] var arr = [2, 5, 4, 6, 8, 8, 2]; var N = arr.length; // Function Call maximumlength(arr, N); </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!