数据结构
网络
关系型数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
安卓
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的求幂和子序列
在这个问题中，给定一个 N 个整数的数组。我们的任务是找出能形成子序列的计数，如果将它们的元素相乘，则得到的数字是 2 的幂。
我们举个例子来理解这个问题，
输入 − arr = [2, 5, 4]
输出 − 3
解释 − 子序列 [2]、[4] 和 [2, 4] 给出了期望的结果。
为了解决这个问题，我们需要理解幂的逻辑。
仅那些为 2 的幂的数字相乘才能给出期望的结果。因此，我们只需考虑数组中本身就是 2 的幂的那些子序列。
因此，如果数组中有 M 个元素是 2 的幂，则子数组的计数为 2M - 1
示例
该程序展示了我们解决方案的实现
#include <iostream>
#include <math.h>
using namespace std;
bool isPowerTwo(int num) {
if (num == 0)
return false;
if (num == 1)
return true;
if (num & (num - 1))
return false;
return true;
}
int SubsequenceWithPowerTwo(int arr[], int N) {
int count = 0;
for (int i = 0; i < N; i++)
if (isPowerTwo(arr[i]))
count++;
return (int)(pow(2, count)) - 1;
}
int main() {
int arr[] = {5, 4, 8, 12, 32, 9 };
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"No. of subsequences which multiply to a number which is a power of 2 are : ";
cout<<SubsequenceWithPowerTwo(arr, N)<<endl;
return 0;
}输出
No. of subsequences which multiply to a number which is a power of 2 are : 7
更新于：2020-04-17
152 次浏览
广告