Frontend School

Dominant Bit in Range Queries

DSA
hard

Dominant Bit in Range Queries

Hard
Bit Manipulation
Prefix Sum
Arrays
Data Structures

Overview

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.

What you need to do / Task

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.

Input & output

  • 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).
  • Returns: An array of integers. Each element in the result array corresponds to a query in the queries input, representing the dominant bit position or -1 if no bits are set in that range.

Clarifications

  • All numbers in 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.
  • If nums is empty, or queries is empty, the function should return an empty array.
  • An empty range (where L > R) will not occur based on constraints.

Examples

1

Example 1

Input:

nums = [1, 2, 3], queries = [[0, 2]]

Output:

[0]

Note:

For nums = [1, 2, 3]:

  • nums[0] = 1 (binary: ...001)
  • nums[1] = 2 (binary: ...010)
  • nums[2] = 3 (binary: ...011) In range [0, 2]:
  • Bit 0 is set in 1 and 3 (count = 2)
  • Bit 1 is set in 2 and 3 (count = 2)
  • Other bits (e.g., bit 2) are set 0 times. Both bit 0 and bit 1 have a max count of 2. The smallest position is 0.
2

Example 2

Input:

nums = [4, 8, 16], queries = [[0, 2]]

Output:

[2]

Note:

For nums = [4, 8, 16]:

  • nums[0] = 4 (binary: ...100)
  • nums[1] = 8 (binary: ...1000)
  • nums[2] = 16 (binary: ...10000) In range [0, 2]:
  • Bit 0 is set 0 times.
  • Bit 1 is set 0 times.
  • Bit 2 is set in 4 (count = 1)
  • Bit 3 is set in 8 (count = 1)
  • Bit 4 is set in 16 (count = 1) All set bits (2, 3, 4) have a count of 1. The smallest position among them is 2.
3

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.

4

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).

  • Bit 0 is set in 1 (count 1).
  • Bit 1 is set in 2 (count 1). Smallest position among max count is 0.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < 2^31
  • 1 <= queries.length <= 10^5
  • 0 <= L <= R < nums.length for all queries [L, R]
  • Time Complexity: O((N + Q) * log(MaxVal)), where N is 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).
  • Space Complexity: O(N * log(MaxVal)) for precomputation.

What interviewers evaluate

  • Correctness in handling bitwise operations and range queries.
  • Efficiency of the solution, demonstrating knowledge of prefix sums or similar optimization techniques for range queries.
  • Clarity of code, including proper variable naming and logical flow.
  • Ability to handle edge cases, such as ranges with no set bits, and ties for the dominant bit position.

Loading editor...