Welcome to Subscribe On Youtube
3145. Find Products of Elements of Big Array
Description
A powerful array for an integer x is the shortest sorted array of powers of two that sum up to x. For example, the powerful array for 11 is [1, 2, 8].
The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so forth. Thus, big_nums starts 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 remainder of 4 under 7 is 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 remainder of 8 under 3 is 2.
Second query: big_nums[7] = 2. The remainder of 2 under 4 is 2.
Constraints:
1 <= queries.length <= 500queries[i].length == 30 <= queries[i][0] <= queries[i][1] <= 10151 <= queries[i][2] <= 105
Solutions
Solution 1
-
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; } } -
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; } }; -
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] -
const m = 50 var cnt [m + 1]int64 var s [m + 1]int64 var p int64 = 1 func init() { cnt[0] = 0 s[0] = 0 for i := 1; i <= m; i++ { cnt[i] = cnt[i-1]*2 + p s[i] = s[i-1]*2 + p*(int64(i)-1) p *= 2 } } func numIdxAndSum(x int64) (int64, int64) { var idx, totalSum int64 for x > 0 { i := 63 - bits.LeadingZeros64(uint64(x)) idx += cnt[i] totalSum += s[i] x -= 1 << i totalSum += (x + 1) * int64(i) idx += x + 1 } return idx, totalSum } func f(i int64) int64 { l, r := int64(0), int64(1)<<m for l < r { mid := (l + r + 1) >> 1 idx, _ := numIdxAndSum(mid) if idx < i { l = mid } else { r = mid - 1 } } _, totalSum := numIdxAndSum(l) idx, _ := numIdxAndSum(l) i -= idx x := l + 1 for j := int64(0); j < i; j++ { y := x & -x totalSum += int64(bits.TrailingZeros64(uint64(y))) x -= y } return totalSum } func qpow(a, n, mod int64) int64 { ans := int64(1) % mod a = a % mod for n > 0 { if n&1 == 1 { ans = (ans * a) % mod } a = (a * a) % mod n >>= 1 } return ans } func findProductsOfElements(queries [][]int64) []int { ans := make([]int, len(queries)) for i, q := range queries { left, right, mod := q[0], q[1], q[2] power := f(right+1) - f(left) ans[i] = int(qpow(2, power, mod)) } return ans }