在本文中,我们将讨论一个问题,即找到给定范围内具有第k位设置的元素的数量,例如 −
Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
0
1
登录后复制
我们将通过一种蛮力的方法来解决这个问题,并看看这种方法是否适用于更高的约束条件。如果不适用,那么我们尝试思考一种新的高效方法。
蛮力方法
在这种方法中,我们只需遍历范围并检查每个元素的第k位是否设置,如果是,则增加计数。
示例
#include
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
if (n & (1