# Find Products of Elements of Big Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-products-of-elements-of-big-array)
Canonical: https://scaleengineer.com/dsa/problems/find-products-of-elements-of-big-array
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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] = [fromi, toi, modi]` you should calculate `(big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi`.

Return an integer array `answer` such that `answer[i]` is the answer to the `ith` 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] <= 1015`
* `1 <= queries[i][2] <= 105`

# Approaches
## Iterative Simulation
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.
**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.
**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.
### Explanation
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:
1.  Initialize a total exponent sum `E = 0`.
2.  Find the starting integer `k` for the index `from` using binary search over the function `L(k)`.
3.  Initialize `current_k = k` and pre-calculate `L(k-1)`.
4.  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`.
5.  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.

```java
// This is a conceptual snippet. A full implementation would require
// helper functions L(k), findK(index), and getMthExponent(k, m).
long totalExponent = 0;
long currentK = findK(from); // Find k for the 'from' index
long lenUntilPrevK = L(currentK - 1);

for (long i = from; i <= to; ++i) {
    long popcountK = Long.bitCount(currentK);
    if (i >= lenUntilPrevK + popcountK) {
        lenUntilPrevK += popcountK;
        currentK++;
    }
    long m = i - lenUntilPrevK + 1;
    int exponent = getMthExponent(currentK, m);
    totalExponent += exponent;
}

long result = power(2, totalExponent, mod);
```
### Algorithm
1. Initialize a total exponent sum `E = 0`.
2. Find the starting integer `k` for the index `from` using binary search over the function `L(k)`.
3. Initialize `current_k = k` and pre-calculate `L(k-1)`.
4. 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`.
5. After the loop, calculate the final result using modular exponentiation: `power(2, E, mod)`.

## Prefix Sum of Exponents with Number Theory
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`.
**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.
**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.
### Explanation
### Algorithm:
1.  **`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.

2.  **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:
```java
// Main logic for a single query
public long solveQuery(long from, long to, int mod) {
    if (mod == 1) return 0;

    long totalExponent = getTotalExponentSum(to) - getTotalExponentSum(from - 1);

    int k = 0;
    int m = mod;
    while (m > 0 && m % 2 == 0) {
        k++;
        m /= 2;
    }
    long mod1 = 1L << k;
    long mod2 = m;

    long rem1 = (totalExponent >= k) ? 0 : power(2, totalExponent, mod1);

    long phi_m = phi(m);
    long exp_mod_phi = totalExponent % phi_m;
    long rem2 = power(2, exp_mod_phi, mod2);

    // Chinese Remainder Theorem to combine results
    if (m == 1) return rem1;
    long inv_mod1 = power(mod1, phi(m) - 1, mod2);
    long c = (rem2 - rem1 + mod2) % mod2;
    c = (c * inv_mod1) % mod2;
    return rem1 + c * mod1;
}

// Recursive function for L(n) - total elements up to n
private long L(long n) {
    if (n <= 0) return 0;
    long p = 63 - Long.numberOfLeadingZeros(n);
    long pow2p = 1L << p;
    long res = p * (1L << (p - 1));
    res += (n - pow2p + 1);
    res += L(n - pow2p);
    return res;
}

// Recursive function for S(n) - total exponent sum up to n
private long S(long n) {
    if (n <= 0) return 0;
    long p = 63 - Long.numberOfLeadingZeros(n);
    long pow2p = 1L << p;
    long res = S_pow2m1(p); // Sum for 1..2^p-1
    res += p * (n - pow2p + 1);
    res += S(n - pow2p);
    return res;
}

private long S_pow2m1(long p) {
    if (p <= 0) return 0;
    return p * (p - 1) / 2 * (1L << (p - 1));
}
```
### Algorithm
1. 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.
2. For each query `[from, to, mod]`, calculate the total exponent `E = get_total_exponent_sum(to) - get_total_exponent_sum(from - 1)`.
3. 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`.

# Solutions
### Java

```java
class Solution {
private
  static final int M = 50;
private
  static final long[] cnt = new long[M + 1];
private
  static final long[] s = new long[M + 1];
  static {
    long p = 1;
    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;
    }
  }
private
  static long[] numIdxAndSum(long x) {
    long idx = 0;
    long totalSum = 0;
    while (x > 0) {
      int i = Long.SIZE - Long.numberOfLeadingZeros(x) - 1;
      idx += cnt[i];
      totalSum += s[i];
      x -= 1L << i;
      totalSum += (x + 1) * i;
      idx += x + 1;
    }
    return new long[]{idx, totalSum};
  }
private
  static long f(long i) {
    long l = 0;
    long r = 1L << M;
    while (l < r) {
      long mid = (l + r + 1) >> 1;
      long[] idxAndSum = numIdxAndSum(mid);
      long idx = idxAndSum[0];
      if (idx < i) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    long[] idxAndSum = numIdxAndSum(l);
    long totalSum = idxAndSum[1];
    long idx = idxAndSum[0];
    i -= idx;
    long x = l + 1;
    for (int j = 0; j < i; j++) {
      long y = x & -x;
      totalSum += Long.numberOfTrailingZeros(y);
      x -= y;
    }
    return totalSum;
  }
public
  int[] findProductsOfElements(long[][] queries) {
    int n = queries.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
      long left = queries[i][0];
      long right = queries[i][1];
      long mod = queries[i][2];
      long power = f(right + 1) - f(left);
      ans[i] = qpow(2, power, mod);
    }
    return ans;
  }
private
  int qpow(long a, long n, long mod) {
    long ans = 1 % mod;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
using 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 ; } };
```

### Python

```python
m = 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 ]
```