3145. Find Products of Elements of Big Array LeetCode Solution
In this guide, you will get 3145. Find Products of Elements of Big Array LeetCode Solution with the best time and space complexity. The solution to Find Products of Elements of Big Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Products of Elements of Big Array
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.
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.
3145. Find Products of Elements of Big Array LeetCode Solution in C++
class Solution {
public:
vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
vector<int> ans;
for (const vector<long long>& query : queries) {
const long a = query[0];
const long b = query[1];
const int mod = query[2];
const int product = modPow(2,
sumPowersFirstKBigNums(b + 1) - //
sumPowersFirstKBigNums(a),
mod);
ans.push_back(product);
}
return ans;
}
private:
// Returns the sum of powers of the first k numbers in `big_nums`.
long sumPowersFirstKBigNums(long k) {
const long num = firstNumberHavingSumBitsTillGreaterThan(k);
long sumPowers = sumPowersTill(num - 1);
long remainingCount = k - sumBitsTill(num - 1);
for (int power = 0; power < bitLength(num); ++power) {
if (num >> power & 1) {
sumPowers += power;
--remainingCount;
if (remainingCount == 0)
break;
}
}
return sumPowers;
}
// Returns the first number in [1, k] that has sumBitsTill(num) >= k.
long firstNumberHavingSumBitsTillGreaterThan(long k) {
long l = 1;
long r = k;
while (l < r) {
const long m = (l + r) / 2;
if (sumBitsTill(m) < k)
l = m + 1;
else
r = m;
}
return l;
}
// Returns sum(i.bit_count()), where 1 <= i <= x.
long sumBitsTill(long x) {
long sumBits = 0;
for (long powerOfTwo = 1; powerOfTwo <= x; powerOfTwo *= 2) {
sumBits += (x / (2L * powerOfTwo)) * powerOfTwo;
sumBits += max(0L, x % (2L * powerOfTwo) + 1 - powerOfTwo);
}
return sumBits;
}
// Returns sum(all powers of i), where 1 <= i <= x.
long sumPowersTill(long x) {
long sumPowers = 0;
long powerOfTwo = 1;
for (int power = 0; power < bitLength(x); ++power) {
sumPowers += (x / (2L * powerOfTwo)) * powerOfTwo * power;
sumPowers += max(0L, x % (2L * powerOfTwo) + 1 - powerOfTwo) * power;
powerOfTwo *= 2;
}
return sumPowers;
}
long modPow(long x, long n, int mod) {
if (n == 0)
return 1 % mod;
if (n % 2 == 1)
return x * modPow(x % mod, (n - 1), mod) % mod;
return modPow(x * x % mod, (n / 2), mod) % mod;
}
int bitLength(long x) {
return x == 0 ? 0 : 64 - __builtin_clzl(x);
}
}; /* code provided by PROGIEZ */
3145. Find Products of Elements of Big Array LeetCode Solution in Java
class Solution {
public int[] findProductsOfElements(long[][] queries) {
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
final long a = queries[i][0];
final long b = queries[i][1];
final int mod = (int) queries[i][2];
ans[i] = (int) modPow(2,
sumPowersFirstKBigNums(b + 1) - //
sumPowersFirstKBigNums(a),
mod);
}
return ans;
}
// Returns the sum of powers of the first k numbers in `big_nums`.
private long sumPowersFirstKBigNums(long k) {
final long num = firstNumberHavingSumBitsTillGreaterThan(k);
long sumPowers = sumPowersTill(num - 1);
long remainingCount = k - sumBitsTill(num - 1);
for (int power = 0; power < bitLength(num); ++power) {
if ((num >> power & 1) == 1) {
sumPowers += power;
--remainingCount;
if (remainingCount == 0)
break;
}
}
return sumPowers;
}
// Returns the first number in [1, k] that has sumBitsTill(num) >= k.
private long firstNumberHavingSumBitsTillGreaterThan(long k) {
long l = 1;
long r = k;
while (l < r) {
final long m = (l + r) / 2;
if (sumBitsTill(m) < k)
l = m + 1;
else
r = m;
}
return l;
}
// Returns sum(i.bit_count()), where 1 <= i <= x.
private long sumBitsTill(long x) {
long sumBits = 0;
for (long powerOfTwo = 1; powerOfTwo <= x; powerOfTwo *= 2) {
sumBits += (x / (2 * powerOfTwo)) * powerOfTwo;
sumBits += Math.max(0, x % (2 * powerOfTwo) + 1 - powerOfTwo);
}
return sumBits;
}
// Returns sum(all powers of i), where 1 <= i <= x.
private long sumPowersTill(long x) {
long sumPowers = 0;
long powerOfTwo = 1;
for (int power = 0; power < bitLength(x); ++power) {
sumPowers += (x / (2 * powerOfTwo)) * powerOfTwo * power;
sumPowers += Math.max(0, x % (2 * powerOfTwo) + 1 - powerOfTwo) * power;
powerOfTwo *= 2;
}
return sumPowers;
}
private long modPow(long x, long n, int mod) {
if (n == 0)
return 1 % mod;
if (n % 2 == 1)
return x * modPow(x % mod, (n - 1), mod) % mod;
return modPow(x * x % mod, (n / 2), mod) % mod;
}
private int bitLength(long x) {
return 64 - Long.numberOfLeadingZeros(x);
}
} // code provided by PROGIEZ
3145. Find Products of Elements of Big Array LeetCode Solution in Python
class Solution:
def findProductsOfElements(self, queries: list[list[int]]) -> list[int]:
def sumBitsTill(x: int) -> int:
"""Returns sum(i.bit_count()), where 1 <= i <= x."""
sumBits = 0
powerOfTwo = 1
while powerOfTwo <= x:
sumBits += (x // (2 * powerOfTwo)) * powerOfTwo
sumBits += max(0, x % (2 * powerOfTwo) + 1 - powerOfTwo)
powerOfTwo *= 2
return sumBits
def sumPowersTill(x: int) -> int:
"""Returns sum(all powers of i), where 1 <= i <= x."""
sumPowers = 0
powerOfTwo = 1
for power in range(x.bit_length()):
sumPowers += (x // (2 * powerOfTwo)) * powerOfTwo * power
sumPowers += max(0, x % (2 * powerOfTwo) + 1 - powerOfTwo) * power
powerOfTwo *= 2
return sumPowers
def sumPowersFirstKBigNums(k: int) -> int:
"""Returns the sum of powers of the first k numbers in `big_nums`."""
# Find the first number in [1, k] that has sumBitsTill(num) >= k.
num = bisect.bisect_left(range(k), k, key=sumBitsTill)
sumPowers = sumPowersTill(num - 1)
remainingCount = k - sumBitsTill(num - 1)
for power in range(num.bit_length()):
if num >> power & 1:
sumPowers += power
remainingCount -= 1
if remainingCount == 0:
break
return sumPowers
return [pow(2,
sumPowersFirstKBigNums(b + 1) -
sumPowersFirstKBigNums(a), mod)
for a, b, mod in queries] # code by PROGIEZ
