Dominant Bit in Range Queries
In complex data analysis, network packet inspection, or even cryptographic applications, efficiently identifying common bit patterns within specified data segments can reveal crucial insights or optimize processing. This problem challenges you to find the most frequently set bit position across a range of numbers, a core operation for certain data analysis tasks that require understanding the 'dominance' of specific bit characteristics.
Implement the function getDominantBit which takes an array of non-negative integers nums and a list of queries. For each query [L, R], you must determine the 0-indexed bit position (from the least significant bit, LSB) that is set to 1 most frequently among all numbers nums[i] where L <= i <= R (inclusive).
If multiple bit positions share the same maximum frequency, you should return the smallest such bit position. If no bits are set to 1 in the entire range (i.e., all numbers in the range are 0), return -1 for that query.
nums: An array of non-negative integers.queries: An array of arrays, where each inner array [L, R] represents a query range (0-indexed, inclusive).queries input, representing the dominant bit position or -1 if no bits are set in that range.nums are non-negative and less than 2^31. This implies that we only need to consider bit positions from 0 up to 30 (inclusive).L and R in queries are 0-indexed and inclusive.nums is empty, or queries is empty, the function should return an empty array.L > R) will not occur based on constraints.Examples
Example 1
Input:
nums = [1, 2, 3], queries = [[0, 2]]
Output:
[0]
Note:
For nums = [1, 2, 3]:
Example 2
Input:
nums = [4, 8, 16], queries = [[0, 2]]
Output:
[2]
Note:
For nums = [4, 8, 16]:
Example 3
Input:
nums = [0, 0, 0], queries = [[0, 2], [1, 1]]
Output:
[-1, -1]
Note:
For both queries, all numbers in the range are 0, meaning no bits are set. Therefore, -1 is returned for both.
Example 4
Input:
nums = [7, 1, 2], queries = [[0, 0], [1, 2]]
Output:
[0, 0]
Note:
Query [0, 0]: nums[0] = 7 (binary: ...111). Bits 0, 1, 2 are all set (count 1). Smallest is 0. Query [1, 2]: nums[1] = 1 (binary: ...001), nums[2] = 2 (binary: ...010).
Constraints
1 <= nums.length <= 10^50 <= nums[i] < 2^311 <= queries.length <= 10^50 <= L <= R < nums.length for all queries [L, R]nums.length, Q is queries.length, and log(MaxVal) is the number of bits to consider (e.g., 31 for numbers less than 2^31).Loading editor...