FastPrep
Problem · Bit Manipulation

Get Query Results

Learn this problem
● MediumIBM logoIBMFULLTIMEOA
See IBM hiring insights

Problem statement

For a positive integer N, its goodArray is the smallest multiset of powers of two whose sum is N. Equivalently, it contains one power of two for every set bit in the binary representation of N. Sort this array in non-decreasing order.

Each query is [l, r, m] and uses 1-based inclusive positions. Compute the product of goodArray[l] through goodArray[r], modulo m.

Return the answers in query order.

Function

getQueryResults(N: long, queries: int[][]) → int[]

Examples

Example 1

N = 26queries = [[1, 2, 1009], [3, 3, 5]]return = [16, 1]

The sorted good array is [2, 8, 16].

  • For [1, 2, 1009], the answer is (2 × 8) mod 1009 = 16.
  • For [3, 3, 5], the answer is 16 mod 5 = 1.

Constraints

  • 1 ≤ N ≤ 10^18
  • 1 ≤ queries.length ≤ 10^5
  • Each query contains exactly three integers [l, r, m].
  • 1 ≤ l ≤ r ≤ goodArray.length
  • 1 ≤ m ≤ 10^5

More IBM problems

drafts saved locally
public int[] getQueryResults(long N, int[][] queries) {
    // Write your code here
}
N26
queries[[1, 2, 1009], [3, 3, 5]]
expected[16, 1]
checking account