Number of powerful Subarrays – GeeksforGeeks
#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n)
{
if (n == 0)
return false;
return (ceil(log2(n)) == floor(log2(n)));
}
void evenOccur(int arr[], int n, int prefixSum[])
{
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];
}
}
void findTwoPowerEven(int s[], int n)
{
int evenCnt[n];
evenOccur(s, n, evenCnt);
int cnt = 0;
int evenInRange = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == 0) {
evenInRange = evenCnt[j];
if (isPowerOfTwo(evenInRange)) {
cnt++;
}
}
else {
evenInRange = evenCnt[j] - evenCnt[i - 1];
if (isPowerOfTwo(evenInRange)) {
cnt++;
}
}
}
}
cout << cnt << endl;
return;
}
signed main()
{
int arr[] = { 1, 2, 4, 2 };
int size = sizeof(arr) / sizeof(int);
cout << "Number of subarrays having power of two "
"times even numbers : ";
findTwoPowerEven(arr, size);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
bool isPowerOfTwo(int n)
{
if (n == 0)
return false;
return (ceil(log2(n)) == floor(log2(n)));
}
void evenOccur(int arr[], int n, int prefixSum[])
{
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];
}
}
void findTwoPowerEven(int s[], int n)
{
int evenCnt[n];
evenOccur(s, n, evenCnt);
int cnt = 0;
int evenInRange = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (i == 0) {
evenInRange = evenCnt[j];
if (isPowerOfTwo(evenInRange)) {
cnt++;
}
}
else {
evenInRange = evenCnt[j] - evenCnt[i - 1];
if (isPowerOfTwo(evenInRange)) {
cnt++;
}
}
}
}
cout << cnt << endl;
return;
}
signed main()
{
int arr[] = { 1, 2, 4, 2 };
int size = sizeof(arr) / sizeof(int);
cout << "Number of subarrays having power of two "
"times even numbers : ";
findTwoPowerEven(arr, size);
return 0;
}
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.