Number of powerful Subarrays
Given an array arr[] of length, N, the task is to find how many powerful subarrays are present in the array.
Note: A powerful subarray is defined as a subarray having the power of two times even numbers. It means the count of even numbers in each subarray will be the power of two (2i where i=0, 1, 2, ….)
Examples:
Input: N = 4, arr[] = { 1, 2, 3, 4 }
Output: 7 Ex: {{2}, {4}, {1, 2}, {2, 3}, {3, 4}, {1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}}Input: N = 4, arr[] = { 1, 2, 4, 2 }
Output: 7 Ex: {{2}, {4}, {2}, {1, 2}, {2, 4}, {4, 2}, {1, 2, 4}}
Naive Approach: The basic way to solve the problem is as follows:
We can find each substring by traversing two nested for loops and then another for loop for counting the number of even numbers and checking the numbers that is it a power of two or not which is O(N3) time Complexity. So we can try another efficient approach.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient approach: To solve the problem follow the below idea:
We can create a precomputed array that counts the occurrence of even numbers. For getting knowledge about precomputing go through presum article. After computing this we can traverse the for loops two times to find the ranges and checking the occurrence between the range is power of two or not. For more clarity follow the process.
Steps to follow the approach:
- Declare a new array evenoccur[] of the same size as the input array.
- Run a for loop to traverse the input array.
- For each index add the value of the previous value of the precomputing array if the element is odd and if the current element is even add the previous element incremented by 1.
- Now we have all occurrences of even numbers till all indexes.
- Now we have to find all the ranges possible. For that traverse a nested for loop.
- In each range find the number of occurring even numbers in this range.
- check whether the number is a power of two or not.
- If it is a power of two, then increment the counter variable.
- After traversing all possible ranges, output the count.
Below is the implementation of the above approach:
C++
// C++ code to implement the same #include <bits/stdc++.h> using namespace std; // Bool function for checking // is power of two bool isPowerOfTwo(int n) { if (n == 0) return false; return (ceil(log2(n)) == floor(log2(n))); } void evenOccur(int arr[], int n, int prefixSum[]) { // Initialize the prefix array if (arr[0] % 2 == 0) { prefixSum[0] = 1; } else { prefixSum[0] = 0; } for (int i = 1; i < n; i++) { if (arr[i] % 2 == 0) prefixSum[i] = prefixSum[i - 1] + 1; // Adding previous element // incremented by 1 else prefixSum[i] = prefixSum[i - 1]; // Adding previous element } } void findTwoPowerEven(int s[], int n) { // Precomputing evenCnt[] array int evenCnt[n]; evenOccur(s, n, evenCnt); // Precomputing the occurrence // of even numbers in evenCnt[] // Counter variabl int cnt = 0; int evenInRange = 0; // For loop for traversing all the // rages for possible subarray for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Counting the occurrence of // even numbers occurrence of // even numbers from i to j is // pre[j]-pre[i-1] if i==0 // then this is pre[j] if (i == 0) { evenInRange = evenCnt[j]; // Incrementing if (isPowerOfTwo(evenInRange)) { cnt++; } } else { evenInRange = evenCnt[j] - evenCnt[i - 1]; if (isPowerOfTwo(evenInRange)) { cnt++; } } } } // Output it cout << cnt << endl; return; } signed main() { int arr[] = { 1, 2, 4, 2 }; // Intitalize the string int size = sizeof(arr) / sizeof(int); cout << "Number of subarrays having power of two " "times even numbers : "; // Calling the function findTwoPowerEven(arr, size); return 0; }
Java
import java.util.*; class Main { // Bool function for checking is power of two static boolean isPowerOfTwo(int n) { if (n == 0) return false; return (Math.ceil(Math.log(n) / Math.log(2)) == Math.floor(Math.log(n) / Math.log(2))); } static void evenOccur(int arr[], int n, int prefixSum[]) { // Initialize the prefix array if (arr[0] % 2 == 0) { prefixSum[0] = 1; } else { prefixSum[0] = 0; } for (int i = 1; i < n; i++) { if (arr[i] % 2 == 0) prefixSum[i] = prefixSum[i - 1] + 1; else prefixSum[i] = prefixSum[i - 1]; } } static void findTwoPowerEven(int s[], int n) { // Precomputing evenCnt[] array int evenCnt[] = new int[n]; evenOccur(s, n, evenCnt); // Precomputing the occurrence of even numbers in evenCnt[] int cnt = 0, evenInRange = 0; // For loop for traversing all the ranges for possible subarray for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Counting the occurrence of even numbers occurrence of even numbers // from i to j is pre[j]-pre[i-1] if i==0 then this is pre[j] if (i == 0) { evenInRange = evenCnt[j]; // Incrementing if (isPowerOfTwo(evenInRange)) { cnt++; } } else { evenInRange = evenCnt[j] - evenCnt[i - 1]; if (isPowerOfTwo(evenInRange)) { cnt++; } } } } // Output it System.out.println("Number of subarrays having power of two times even numbers: " + cnt); return; } public static void main(String[] args) { int arr[] = { 1, 2, 4, 2 }; int size = arr.length; // Calling the function findTwoPowerEven(arr, size); } }
Python3
import math # Function to check if a number is power of two def isPowerOfTwo(n): if n == 0: return False return (math.ceil(math.log2(n)) == math.floor(math.log2(n))) # Function to calculate prefix sum of even numbers def evenOccur(arr, n, prefixSum): if arr[0] % 2 == 0: prefixSum[0] = 1 else: prefixSum[0] = 0 for i in range(1, n): if arr[i] % 2 == 0: prefixSum[i] = prefixSum[i-1] + 1 else: prefixSum[i] = prefixSum[i-1] # Main function to find subarrays with power of two times even numbers def findTwoPowerEven(arr, n): evenCnt = [0] * n evenOccur(arr, n, evenCnt) cnt = 0 evenInRange = 0 for i in range(n): for j in range(i, n): if i == 0: evenInRange = evenCnt[j] if isPowerOfTwo(evenInRange): cnt += 1 else: evenInRange = evenCnt[j] - evenCnt[i-1] if isPowerOfTwo(evenInRange): cnt += 1 print("Number of subarrays having power of two times even numbers:", cnt) # Driver code arr = [1, 2, 4, 2] size = len(arr) findTwoPowerEven(arr, size)
C#
using System; class MainClass { // Bool function for checking is power of two static bool IsPowerOfTwo(int n) { if (n == 0) return false; return (Math.Ceiling(Math.Log(n) / Math.Log(2)) == Math.Floor(Math.Log(n) / Math.Log(2))); } static void EvenOccur(int[] arr, int n, int[] prefixSum) { // Initialize the prefix array if (arr[0] % 2 == 0) prefixSum[0] = 1; else prefixSum[0] = 0; for (int i = 1; i < n; i++) { if (arr[i] % 2 == 0) prefixSum[i] = prefixSum[i - 1] + 1; else prefixSum[i] = prefixSum[i - 1]; } } static void FindTwoPowerEven(int[] s, int n) { // Precomputing evenCnt[] array int[] evenCnt = new int[n]; EvenOccur(s, n, evenCnt); // Precomputing the occurrence of even numbers in // evenCnt[] int cnt = 0, evenInRange = 0; // For loop for traversing all the ranges for // possible subarray for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Counting the occurrence of even numbers // occurrence of even numbers from i to j is // pre[j]-pre[i-1] if i==0 then this is // pre[j] if (i == 0) { evenInRange = evenCnt[j]; // Incrementing if (IsPowerOfTwo(evenInRange)) cnt++; } else { evenInRange = evenCnt[j] - evenCnt[i - 1]; if (IsPowerOfTwo(evenInRange)) cnt++; } } } // Output it Console.WriteLine( "Number of subarrays having power of two times even numbers: " + cnt); return; } static void Main(string[] args) { int[] arr = { 1, 2, 4, 2 }; int size = arr.Length; // Calling the function FindTwoPowerEven(arr, size); } }
Javascript
// Function for checking if a number is a power of two function isPowerOfTwo(n) { if (n == 0) { return false; } return Math.ceil(Math.log2(n)) == Math.floor(Math.log2(n)); } // Function to compute prefix sum of even numbers in an array function evenOccur(arr, n, prefixSum) { // Initialize the prefix array if (arr[0] % 2 == 0) { prefixSum[0] = 1; } else { prefixSum[0] = 0; } for (let i = 1; i < n; i++) { if (arr[i] % 2 == 0) { prefixSum[i] = prefixSum[i - 1] + 1; } else { prefixSum[i] = prefixSum[i - 1]; } } } // Function to find subarrays with power of two times even numbers function findTwoPowerEven(s, n) { // Precomputing evenCnt[] array const evenCnt = new Array(n); evenOccur(s, n, evenCnt); // Precomputing the occurrence of even numbers in evenCnt[] // Counter variable let cnt = 0; let evenInRange = 0; // For loop for traversing all the ranges for possible subarray for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { // Counting the occurrence of even numbers from i to j // even numbers occurrence from i to j is pre[j] - pre[i-1] if i == 0 then this is pre[j] if (i == 0) { evenInRange = evenCnt[j]; // Incrementing if (isPowerOfTwo(evenInRange)) { cnt++; } } else { evenInRange = evenCnt[j] - evenCnt[i - 1]; if (isPowerOfTwo(evenInRange)) { cnt++; } } } } // Output the result console.log("Number of subarrays having power of two times even numbers: " + cnt); } // Sample input const arr = [1, 2, 4, 2]; const size = arr.length; // Calling the function findTwoPowerEven(arr, size);
Number of subarrays having power of two times even numbers : 7
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us