3539. Find Sum of Array Product of Magical Sequences LeetCode Solution
In this guide, you will get 3539. Find Sum of Array Product of Magical Sequences LeetCode Solution with the best time and space complexity. The solution to Find Sum of Array Product of Magical Sequences 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.
Table of Contents
- Problem Statement
- Complexity Analysis
- Find Sum of Array Product of Magical Sequences solution in C++
- Find Sum of Array Product of Magical Sequences solution in Java
- Find Sum of Array Product of Magical Sequences solution in Python
- Additional Resources
Problem Statement of Find Sum of Array Product of Magical Sequences
You are given two integers, m and k, and an integer array nums.
A sequence of integers seq is called magical if:
seq has a size of m.
0 <= seq[i] < nums.length
The binary representation of 2seq[0] + 2seq[1] + … + 2seq[m – 1] has k set bits.
The array product of this sequence is defined as prod(seq) = (nums[seq[0]] * nums[seq[1]] * … * nums[seq[m – 1]]).
Return the sum of the array products for all valid magical sequences.
Since the answer may be large, return it modulo 109 + 7.
A set bit refers to a bit in the binary representation of a number that has a value of 1.
Example 1:
Input: m = 5, k = 5, nums = [1,10,100,10000,1000000]
Output: 991600007
Explanation:
All permutations of [0, 1, 2, 3, 4] are magical sequences, each with an array product of 1013.
Example 2:
Input: m = 2, k = 2, nums = [5,4,3,2,1]
Output: 170
Explanation:
The magical sequences are [0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], and [4, 3].
Example 3:
Input: m = 1, k = 1, nums = [28]
Output: 28
Explanation:
The only magical sequence is [0].
Constraints:
1 <= k <= m <= 30
1 <= nums.length <= 50
1 <= nums[i] <= 108
Complexity Analysis
- Time Complexity: O(m^3kn)
- Space Complexity: O(m^2kn)
3539. Find Sum of Array Product of Magical Sequences LeetCode Solution in C++
class Solution {
public:
int magicalSum(int m, int k, vector<int>& nums) {
const vector<vector<int>> comb = getComb(m, m);
vector<vector<vector<vector<int>>>> mem(
m + 1, vector<vector<vector<int>>>(
k + 1, vector<vector<int>>(nums.size() + 1,
vector<int>(m + 1, -1))));
return dp(m, k, 0, 0, nums, mem, comb);
}
private:
static constexpr int kMod = 1'000'000'007;
int dp(int m, int k, int i, unsigned carry, const vector<int>& nums,
vector<vector<vector<vector<int>>>>& mem,
const vector<vector<int>>& comb) {
if (m < 0 || k < 0 || (m + popcount(carry) < k))
return 0;
if (m == 0)
return k == popcount(carry) ? 1 : 0;
if (i == nums.size())
return 0;
if (mem[m][k][i][carry] != -1)
return mem[m][k][i][carry];
int res = 0;
for (int count = 0; count <= m; ++count) {
const long contribution = comb[m][count] * modPow(nums[i], count) % kMod;
const int newCarry = carry + count;
res = (res + static_cast<long>(dp(m - count, k - (newCarry % 2), i + 1,
newCarry / 2, nums, mem, comb)) *
contribution) %
kMod;
}
return mem[m][k][i][carry] = res;
}
// C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
vector<vector<int>> getComb(int n, int k) {
vector<vector<int>> comb(n + 1, vector<int>(k + 1));
for (int i = 0; i <= n; ++i)
comb[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j)
comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
return comb;
}
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
};
/* code provided by PROGIEZ */3539. Find Sum of Array Product of Magical Sequences LeetCode Solution in Java
class Solution {
public int magicalSum(int m, int k, int[] nums) {
int[][] comb = getComb(m, m);
Integer[][][][] mem = new Integer[m + 1][k + 1][nums.length + 1][m + 1];
return dp(m, k, 0, 0, nums, mem, comb);
}
private static final int MOD = 1_000_000_007;
private int dp(int m, int k, int i, int carry, int[] nums, Integer[][][][] mem, int[][] comb) {
if (m < 0 || k < 0 || (m + Integer.bitCount(carry) < k))
return 0;
if (m == 0)
return k == Integer.bitCount(carry) ? 1 : 0;
if (i == nums.length)
return 0;
if (mem[m][k][i][carry] != null)
return mem[m][k][i][carry];
int res = 0;
for (int count = 0; count <= m; count++) {
final long contribution = comb[m][count] * modPow(nums[i], count) % MOD;
final int newCarry = carry + count;
res = (int) ((res +
(long) dp(m - count, k - (newCarry % 2), i + 1, newCarry / 2, nums, mem, comb) *
contribution) %
MOD);
}
return mem[m][k][i][carry] = res;
}
// C(n, k) = C(n - 1, k) + C(n - 1, k - 1)
private int[][] getComb(int n, int k) {
int[][] comb = new int[n + 1][k + 1];
for (int i = 0; i <= n; i++)
comb[i][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
return comb;
}
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % MOD, n - 1) % MOD;
return modPow(x * x % MOD, n / 2) % MOD;
}
}
// code provided by PROGIEZ3539. Find Sum of Array Product of Magical Sequences LeetCode Solution in Python
class Solution:
def magicalSum(self, m: int, k: int, nums: list[int]) -> int:
MOD = 1_000_000_007
@functools.lru_cache(None)
def dp(m: int, k: int, i: int, carry: int) -> int:
"""
Returns the number of magical sequences of length `k` that can be formed
from the first `i` numbers in `nums` with at most `m` elements.
"""
if m < 0 or k < 0 or (m + carry.bit_count() < k):
return 0
if m == 0:
return int(k == carry.bit_count())
if i == len(nums):
return 0
res = 0
for count in range(m + 1):
contribution = math.comb(m, count) * pow(nums[i], count, MOD) % MOD
newCarry = carry + count
res += dp(m - count, k - (newCarry % 2),
i + 1, newCarry // 2) * contribution
res %= MOD
return res
return dp(m, k, 0, 0)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.