在给定的问题中,我们需要找到一个数字的值,该数字具有给定范围 L、R 之间的所有设置位。例如 -
Input: L = 1, R = 5 Output: 62 Explanation: representation of given L and R in binary form is 0..0111110 Input: L = 1, R = 4 Output: 30 Explanation: representation of given L and R in binary form is 0..11110
在给定的问题中,我们将讨论两种方法,蛮力方法和高效方法。
在这种方法中,我们只需遍历给定的范围并在给定的范围内添加 2 的所有幂,这就是我们的答案。
#include<bits/stdc++.h> using namespace std; int main() { int L = 1, R = 3; // 给定的范围 int ans = 0; // 我们的回答 for(int i = L; i <= R; i++) // 穿越整个范围 ans += pow(2, i); // 为答案添加值。 cout << ans << "\n"; }输出结果
14
在这种方法中,我们只是遍历范围并简单地添加范围内数字的 2 的幂。该程序的时间复杂度为O(N),其中 N 是我们范围的大小。但是我们可以通过在给定问题中应用位的知识来进一步提高时间复杂度。
在这种方法中,我们将简单地制定一个公式来计算我们的答案。
#include<bits/stdc++.h> using namespace std; int main() { int L = 1, R = 3; // 给定的范围 int ans = 0; // 我们的回答 for(int i = L; i <= R; i++) // 穿越整个范围 ans += pow(2, i); // 为答案添加值。 cout << ans << "\n"; }输出结果
14
在这种方法中,我们制定了一个公式来计算我们的答案。
如您所知,我们需要计算给定范围内设置位的数字,因此在这种方法中,我们找到一个数字,其所有位都设置为从 0 到 R。然后我们需要减去一个具有所有位的数字设置从 1 到 (L-1),因此我们制定了这个观察。给定代码的总时间复杂度为O(1),这是常数时间复杂度,这意味着我们可以在常数时间内计算出任何答案。
本文将为“仅在第 L 个和第 R 个索引之间设置位的数字”编写一个程序。我们还学习了针对此问题的 C++ 程序以及我们解决此问题的完整方法(正常和高效)。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。我们希望这篇文章对您有所帮助。