資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告