資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中使用 1 到 n 的 K 個數字求最大異或
在這個問題中，我們給定兩個正整數 n 和 k。我們的任務是找到使用最多 X 個數字從 1 到 n 之間的最大異或。
讓我們舉個例子來理解這個問題，
輸入 − n = 5, k = 2
輸出 − 7
解釋 −
elements till 5 is 1, 2, 3, 4, 5 Selecting all XOR pairs: 1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4 2^3 = 4, 2^4 = 6, 2^5 = 7 3^4 = 7, 3^5 = 6 4^5 = 1 The maximum here is 7.
為了解決這個問題，可以發現任何數字組合的最大異或是在數字的所有位都設定為 1 時找到的。
所以，如果數字是 5，它的二進位制是 101，最大異或將是 111，即 7。
但是，如果要取的最大異或的元素個數為 1，則最大異或為 1。否則，最大異或將透過將所有位設定為 1 來找到。
示例
程式說明我們解決方案的工作原理，
#include <iostream>
using namespace std;
int maxXor(int n, int k) {
if (k == 1)
return n;
int result = 1;
while (result <= n)
result <<= 1;
return result - 1;
}
int main() {
int n = 5, k = 2;
cout<<"The maximum XOR of "<<k<<" numbers from 1 to"<<n<<" is "<<maxXor(n, k);
return 0;
}輸出
The maximum XOR of 2 numbers from 1 to 5 is 7
更新於: 2020年6月3日
321 次檢視
廣告