Find Products of Elements of Big Array

Hard

#2794Time: O((log N)^2 + (to - from) * log k), where N is the maximum value of `to`, and `k` is the integer corresponding to index `to`. The `(log N)^2` part is for the initial binary search, and the rest is for the loop. This is too slow for the given constraints.Space: O(log N) for the recursion stack of helper functions.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The table below illustrates examples of how the powerful array is determined. It can be proven that the powerful array of x is unique.

num	Binary Representation	powerful array
1	00001	[1]
8	01000	[8]
10	01010	[2, 8]
13	01101	[1, 4, 8]
23	10111	[1, 2, 4, 16]

The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...].

You are given a 2D integer matrix queries, where for queries[i] = [from_i, to_i, mod_i] you should calculate (big_nums[from_i] * big_nums[from_i + 1] * ... * big_nums[to_i]) % mod_i.

Return an integer array answer such that answer[i] is the answer to the i^th query.

Example 1:

Input: queries = [[1,3,7]]

Output: [4]

Explanation:

There is one query.

big_nums[1..3] = [2,1,2]. The product of them is 4. The result is 4 % 7 = 4.

Example 2:

Input: queries = [[2,5,3],[7,7,4]]

Output: [2,2]

Explanation:

There are two queries.

First query: big_nums[2..5] = [1,2,4,1]. The product of them is 8. The result is 8 % 3 = 2.

Second query: big_nums[7] = 2. The result is 2 % 4 = 2.

Constraints:

1 <= queries.length <= 500
queries[i].length == 3
0 <= queries[i][0] <= queries[i][1] <= 10¹⁵
1 <= queries[i][2] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but less efficient approach is to simulate the process directly. For a given query [from, to, mod], we can iterate from the index from to to. For each index i, we determine the corresponding value big_nums[i] and include it in our product calculation. Since all values in big_nums are powers of two, we can sum their exponents and then perform a single modular exponentiation at the end.

Algorithm

Initialize a total exponent sum E = 0.
Find the starting integer k for the index from using binary search over the function L(k).
Initialize current_k = k and pre-calculate L(k-1).
Iterate with an index i from from to to: a. Check if i has moved past the elements of current_k. If so, update L(k-1) and increment current_k. b. Calculate the position m = i - L(k-1) + 1. c. Find the exponent of the m-th element of current_k's powerful array (i.e., the position of the m-th set bit of current_k). d. Add this exponent to E.
After the loop, calculate the final result using modular exponentiation: power(2, E, mod).

Walkthrough

To find the value big_nums[i], we first need to identify which integer's powerful array it belongs to. Let L(k) be the total length of big_nums after concatenating the powerful arrays for integers 1 through k. L(k) is the sum of the population counts (number of set bits) of all integers from 1 to k. We can find the integer k corresponding to index i by finding k such that L(k-1) <= i < L(k). This can be done via binary search.

Once k is found, big_nums[i] is the (i - L(k-1) + 1)-th element of the powerful array of k. The powerful array's elements correspond to the set bits of k, so we find the (i - L(k-1) + 1)-th set bit of k. If this bit is at position p (0-indexed), the value is 2^p, and its exponent is p.

To optimize the iteration from from to to, instead of performing a binary search for each i, we can find the starting k for from and then simply increment k as we cross the boundary of its powerful array's elements in big_nums.

Algorithm:

Initialize a total exponent sum E = 0.
Find the starting integer k for the index from using binary search over the function L(k).
Initialize current_k = k and pre-calculate L(k-1).
Iterate with an index i from from to to: a. Check if i has moved past the elements of current_k. If so, update L(k-1) and increment current_k. b. Calculate the position m = i - L(k-1) + 1. c. Find the exponent of the m-th element of current_k's powerful array (i.e., the position of the m-th set bit of current_k). d. Add this exponent to E.
After the loop, calculate the final result using modular exponentiation: power(2, E, mod).

This approach is too slow for the given constraints because the range to - from can be very large, leading to a timeout.

1// This is a conceptual snippet. A full implementation would require2// helper functions L(k), findK(index), and getMthExponent(k, m).3long totalExponent = 0;4long currentK = findK(from); // Find k for the 'from' index5long lenUntilPrevK = L(currentK - 1);6 7for (long i = from; i <= to; ++i) {8    long popcountK = Long.bitCount(currentK);9    if (i >= lenUntilPrevK + popcountK) {10        lenUntilPrevK += popcountK;11        currentK++;12    }13    long m = i - lenUntilPrevK + 1;14    int exponent = getMthExponent(currentK, m);15    totalExponent += exponent;16}17 18long result = power(2, totalExponent, mod);

Complexity

Time

O((log N)^2 + (to - from) * log k), where N is the maximum value of `to`, and `k` is the integer corresponding to index `to`. The `(log N)^2` part is for the initial binary search, and the rest is for the loop. This is too slow for the given constraints.

Space

O(log N) for the recursion stack of helper functions.

Trade-offs

Pros

Conceptually simpler than the optimal solution.
Works for smaller constraints on the range to - from.

Cons

Inefficient for large ranges [from, to], as it involves a loop of up to 10^15 iterations in the worst case, which will time out.

The most efficient approach avoids iterating through the large range [from, to]. The key insight is that the product of powers of two, 2^p1 * 2^p2 * ..., is simply 2^(p1+p2+...). Thus, the problem reduces to finding the sum of exponents of the elements in big_nums[from...to]. This sum can be computed using prefix sums: sum_exponents(0, to) - sum_exponents(0, from-1).

We can define a function, get_total_exponent_sum(N), to calculate the sum of exponents of all elements from big_nums[0] to big_nums[N]. This function itself relies on two helper functions, L(k) (total elements for numbers 1..k) and S(k) (total sum of exponents for numbers 1..k). We can derive efficient recursive formulas for L(k) and S(k) that work for large k by considering the binary representation of k.

Algorithm

Define a function get_total_exponent_sum(N) that computes the sum of exponents of big_nums[0...N]. a. This function uses helper functions L(k) (total elements for numbers 1..k) and S(k) (total exponent sum for 1..k), which are implemented with efficient O(log k) recursions. b. It finds the number k corresponding to index N via binary search. c. It combines S(k-1) with the exponent sum from the prefix of k's powerful array.
For each query [from, to, mod], calculate the total exponent E = get_total_exponent_sum(to) - get_total_exponent_sum(from - 1).
Calculate 2^E % mod using number theory: a. Decompose mod = 2^k * m where m is odd. b. Solve the system of congruences x ≡ 2^E (mod 2^k) and x ≡ 2^E (mod m) using the Chinese Remainder Theorem (CRT). c. Use Euler's totient theorem for the congruence modulo m.

Walkthrough

Algorithm:

get_total_exponent_sum(N) function: a. First, find the integer k such that index N falls within its powerful array. This is done by binary searching for k where L(k-1) <= N < L(k). b. The total sum of exponents up to N is the sum of exponents for all numbers up to k-1, which is S(k-1), plus the sum of exponents for the first M = N - L(k-1) + 1 elements of k's powerful array. c. L(k) and S(k) are computed using efficient recursive functions that operate in O(log k) time. These functions must use 64-bit integers to handle large inputs.
Main Query Logic: a. For a query [from, to, mod], calculate the total exponent E = get_total_exponent_sum(to) - get_total_exponent_sum(from - 1). b. The result is 2^E % mod. Since E can be enormous, we cannot compute 2^E directly. We use number theory. c. Factor the modulus mod into 2^k * m, where m is odd. d. Use the Chinese Remainder Theorem (CRT) to solve the system of congruences: - x ≡ 2^E (mod 2^k) - x ≡ 2^E (mod m) e. The first congruence x ≡ 2^E (mod 2^k) evaluates to 0 if E >= k, and 2^E otherwise. We can compute E exactly to check this. f. The second congruence x ≡ 2^E (mod m) is solved using Euler's totient theorem: x ≡ 2^(E % phi(m)) (mod m). g. Combine the two results using the CRT formula to find the final answer x.

Code Snippets:

1// Main logic for a single query2public long solveQuery(long from, long to, int mod) {3    if (mod == 1) return 0;4 5    long totalExponent = getTotalExponentSum(to) - getTotalExponentSum(from - 1);6 7    int k = 0;8    int m = mod;9    while (m > 0 && m % 2 == 0) {10        k++;11        m /= 2;12    }13    long mod1 = 1L << k;14    long mod2 = m;15 16    long rem1 = (totalExponent >= k) ? 0 : power(2, totalExponent, mod1);17 18    long phi_m = phi(m);19    long exp_mod_phi = totalExponent % phi_m;20    long rem2 = power(2, exp_mod_phi, mod2);21 22    // Chinese Remainder Theorem to combine results23    if (m == 1) return rem1;24    long inv_mod1 = power(mod1, phi(m) - 1, mod2);25    long c = (rem2 - rem1 + mod2) % mod2;26    c = (c * inv_mod1) % mod2;27    return rem1 + c * mod1;28}29 30// Recursive function for L(n) - total elements up to n31private long L(long n) {32    if (n <= 0) return 0;33    long p = 63 - Long.numberOfLeadingZeros(n);34    long pow2p = 1L << p;35    long res = p * (1L << (p - 1));36    res += (n - pow2p + 1);37    res += L(n - pow2p);38    return res;39}40 41// Recursive function for S(n) - total exponent sum up to n42private long S(long n) {43    if (n <= 0) return 0;44    long p = 63 - Long.numberOfLeadingZeros(n);45    long pow2p = 1L << p;46    long res = S_pow2m1(p); // Sum for 1..2^p-147    res += p * (n - pow2p + 1);48    res += S(n - pow2p);49    return res;50}51 52private long S_pow2m1(long p) {53    if (p <= 0) return 0;54    return p * (p - 1) / 2 * (1L << (p - 1));55}

Complexity

Time

O(Q * (log N)^2), where Q is the number of queries and N is the maximum value of `to_i`. The `(log N)^2` factor comes from the binary search inside `get_total_exponent_sum`, where each step involves a call to `L(k)` which takes `O(log k)` time.

Space

O(log N) due to the recursion depth of the helper functions.

Trade-offs

Pros

Highly efficient, capable of handling the large constraints on from and to.
Mathematically elegant solution.

Cons

Significantly more complex to understand and implement.
Requires knowledge of advanced number theory concepts like Euler's totient theorem and the Chinese Remainder Theorem.

Solutions

Solution

1class Solution {2private3  static final int M = 50;4private5  static final long[] cnt = new long[M + 1];6private7  static final long[] s = new long[M + 1];8  static {9    long p = 1;10    for (int i = 1; i <= M; i++) {11      cnt[i] = cnt[i - 1] * 2 + p;12      s[i] = s[i - 1] * 2 + p * (i - 1);13      p *= 2;14    }15  }16private17  static long[] numIdxAndSum(long x) {18    long idx = 0;19    long totalSum = 0;20    while (x > 0) {21      int i = Long.SIZE - Long.numberOfLeadingZeros(x) - 1;22      idx += cnt[i];23      totalSum += s[i];24      x -= 1L << i;25      totalSum += (x + 1) * i;26      idx += x + 1;27    }28    return new long[]{idx, totalSum};29  }30private31  static long f(long i) {32    long l = 0;33    long r = 1L << M;34    while (l < r) {35      long mid = (l + r + 1) >> 1;36      long[] idxAndSum = numIdxAndSum(mid);37      long idx = idxAndSum[0];38      if (idx < i) {39        l = mid;40      } else {41        r = mid - 1;42      }43    }44    long[] idxAndSum = numIdxAndSum(l);45    long totalSum = idxAndSum[1];46    long idx = idxAndSum[0];47    i -= idx;48    long x = l + 1;49    for (int j = 0; j < i; j++) {50      long y = x & -x;51      totalSum += Long.numberOfTrailingZeros(y);52      x -= y;53    }54    return totalSum;55  }56public57  int[] findProductsOfElements(long[][] queries) {58    int n = queries.length;59    int[] ans = new int[n];60    for (int i = 0; i < n; i++) {61      long left = queries[i][0];62      long right = queries[i][1];63      long mod = queries[i][2];64      long power = f(right + 1) - f(left);65      ans[i] = qpow(2, power, mod);66    }67    return ans;68  }69private70  int qpow(long a, long n, long mod) {71    long ans = 1 % mod;72    for (; n > 0; n >>= 1) {73      if ((n & 1) == 1) {74        ans = ans * a % mod;75      }76      a = a * a % mod;77    }78    return (int)ans;79  }80}

1using ll = long long ; const int m = 50 ; ll cnt [ m + 1 ]; ll s [ m + 1 ]; ll p = 1 ; auto init = [] { cnt [ 0 ] = 0 ; s [ 0 ] = 0 ; for ( int i = 1 ; i <= m ; ++ i ) { cnt [ i ] = cnt [ i - 1 ] * 2 + p ; s [ i ] = s [ i - 1 ] * 2 + p * ( i - 1 ); p *= 2 ; } return 0 ; }(); pair < ll , ll > numIdxAndSum ( ll x ) { ll idx = 0 ; ll totalSum = 0 ; while ( x > 0 ) { int i = 63 - __builtin_clzll ( x ); idx += cnt [ i ]; totalSum += s [ i ]; x -= 1LL << i ; totalSum += ( x + 1 ) * i ; idx += x + 1 ; } return make_pair ( idx , totalSum ); } ll f ( ll i ) { ll l = 0 ; ll r = 1LL << m ; while ( l < r ) { ll mid = ( l + r + 1 ) >> 1 ; auto idxAndSum = numIdxAndSum ( mid ); ll idx = idxAndSum . first ; if ( idx < i ) { l = mid ; } else { r = mid - 1 ; } } auto idxAndSum = numIdxAndSum ( l ); ll totalSum = idxAndSum . second ; ll idx = idxAndSum . first ; i -= idx ; ll x = l + 1 ; for ( int j = 0 ; j < i ; ++ j ) { ll y = x & - x ; totalSum += __builtin_ctzll ( y ); x -= y ; } return totalSum ; } ll qpow ( ll a , ll n , ll mod ) { ll ans = 1 % mod ; a = a % mod ; while ( n > 0 ) { if ( n & 1 ) { ans = ans * a % mod ; } a = a * a % mod ; n >>= 1 ; } return ans ; } class Solution { public: vector < int > findProductsOfElements ( vector < vector < ll >>& queries ) { int n = queries . size (); vector < int > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { ll left = queries [ i ][ 0 ]; ll right = queries [ i ][ 1 ]; ll mod = queries [ i ][ 2 ]; ll power = f ( right + 1 ) - f ( left ); ans [ i ] = static_cast < int > ( qpow ( 2 , power , mod )); } return ans ; } };

1m = 50 cnt = [ 0 ] * ( m + 1 ) s = [ 0 ] * ( m + 1 ) p = 1 for i in range ( 1 , m + 1 ): cnt [ i ] = cnt [ i - 1 ] * 2 + p s [ i ] = s [ i - 1 ] * 2 + p * ( i - 1 ) p *= 2 def num_idx_and_sum ( x : int ) -> tuple : idx = 0 total_sum = 0 while x : i = x . bit_length () - 1 idx += cnt [ i ] total_sum += s [ i ] x -= 1 << i total_sum += ( x + 1 ) * i idx += x + 1 return ( idx , total_sum ) def f ( i : int ) -> int : l , r = 0 , 1 << m while l < r : mid = ( l + r + 1 ) >> 1 idx , _ = num_idx_and_sum ( mid ) if idx < i : l = mid else : r = mid - 1 total_sum = 0 idx , total_sum = num_idx_and_sum ( l ) i -= idx x = l + 1 for _ in range ( i ): y = x & - x total_sum += y . bit_length () - 1 x -= y return total_sum class Solution : def findProductsOfElements ( self , queries : List [ List [ int ]]) -> List [ int ]: return [ pow ( 2 , f ( right + 1 ) - f ( left ), mod ) for left , right , mod in queries ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem