3098. Find the Sum of Subsequence Powers LeetCode Solution
In this guide, you will get 3098. Find the Sum of Subsequence Powers LeetCode Solution with the best time and space complexity. The solution to Find the Sum of Subsequence Powers 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 the Sum of Subsequence Powers solution in C++
- Find the Sum of Subsequence Powers solution in Java
- Find the Sum of Subsequence Powers solution in Python
- Additional Resources
Problem Statement of Find the Sum of Subsequence Powers
You are given an integer array nums of length n, and a positive integer k.
The power of a subsequence is defined as the minimum absolute difference between any two elements in the subsequence.
Return the sum of powers of all subsequences of nums which have length equal to k.
Since the answer may be large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4], k = 3
Output: 4
Explanation:
There are 4 subsequences in nums which have length 3: [1,2,3], [1,3,4], [1,2,4], and [2,3,4]. The sum of powers is |2 – 3| + |3 – 4| + |2 – 1| + |3 – 4| = 4.
Example 2:
Input: nums = [2,2], k = 2
Output: 0
Explanation:
The only subsequence in nums which has length 2 is [2,2]. The sum of powers is |2 – 2| = 0.
Example 3:
Input: nums = [4,3,-1], k = 2
Output: 10
Explanation:
There are 3 subsequences in nums which have length 2: [4,3], [4,-1], and [3,-1]. The sum of powers is |4 – 3| + |4 – (-1)| + |3 – (-1)| = 10.
Constraints:
2 <= n == nums.length <= 50
-108 <= nums[i] <= 108
2 <= k <= n
Complexity Analysis
- Time Complexity: O(n^4k)
- Space Complexity: O(n^3k)
3098. Find the Sum of Subsequence Powers LeetCode Solution in C++
class Solution {
public:
int sumOfPowers(vector<int>& nums, int k) {
const int n = nums.size();
ranges::sort(nums);
vector<vector<vector<vector<int>>>> mem(
n + 1, vector<vector<vector<int>>>(
n + 1, vector<vector<int>>(n + 1, vector<int>(k + 1, -1))));
return sumOfPowers(nums, 0, k, -1, -1, -1, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the sum of powers of all subsequences of nums[i..n) which
// have length equal to k, where `lastPickedIndex` is the index of the last
// picked number and nums[secondIndex] - nums[firstIndex] is the minimum power
// so far.
int sumOfPowers(const vector<int>& nums, int i, int k, int lastPickedIndex,
int firstIndex, int secondIndex,
vector<vector<vector<vector<int>>>>& mem) {
if (k == 0)
return nums[secondIndex] - nums[firstIndex];
if (i == nums.size())
return 0;
const int a = hash(lastPickedIndex);
const int b = hash(firstIndex);
const int c = hash(secondIndex);
if (mem[a][b][c][k] != -1)
return mem[a][b][c][k];
int newFirstIndex = firstIndex;
int newSecondIndex = secondIndex;
if (firstIndex == -1) {
newFirstIndex = i;
} else if (secondIndex == -1) {
newSecondIndex = i;
} else if (nums[i] - nums[lastPickedIndex] <
nums[secondIndex] - nums[firstIndex]) {
newFirstIndex = lastPickedIndex;
newSecondIndex = i;
}
const int pick =
sumOfPowers(nums, i + 1, k - 1, i, newFirstIndex, newSecondIndex, mem);
const int skip = sumOfPowers(nums, i + 1, k, lastPickedIndex, firstIndex,
secondIndex, mem);
return mem[a][b][c][k] = (pick + skip) % kMod;
}
constexpr int hash(int x) {
return x + 1;
}
};
/* code provided by PROGIEZ */3098. Find the Sum of Subsequence Powers LeetCode Solution in Java
class Solution {
public int sumOfPowers(int[] nums, int k) {
final int n = nums.length;
Arrays.sort(nums);
Integer[][][][] mem = new Integer[n + 1][n + 1][n + 1][k + 1];
return sumOfPowers(nums, 0, k, -1, -1, -1, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the sum of powers of all subsequences of nums[i..n) which
// have length equal to k, where `lastPickedIndex` is the index of the last
// picked number and nums[secondIndex] - nums[firstIndex] is the minimum power
// so far.
private int sumOfPowers(int[] nums, int i, int k, int lastPickedIndex, int firstIndex,
int secondIndex, Integer[][][][] mem) {
if (k == 0)
return nums[secondIndex] - nums[firstIndex];
if (i == nums.length)
return 0;
final int a = hash(lastPickedIndex);
final int b = hash(firstIndex);
final int c = hash(secondIndex);
if (mem[a][b][c][k] != null)
return mem[a][b][c][k];
int newFirstIndex = firstIndex;
int newSecondIndex = secondIndex;
if (firstIndex == -1) {
newFirstIndex = i;
} else if (secondIndex == -1) {
newSecondIndex = i;
} else if (nums[i] - nums[lastPickedIndex] < nums[secondIndex] - nums[firstIndex]) {
newFirstIndex = lastPickedIndex;
newSecondIndex = i;
}
final int pick = sumOfPowers(nums, i + 1, k - 1, i, newFirstIndex, newSecondIndex, mem);
final int skip = sumOfPowers(nums, i + 1, k, lastPickedIndex, firstIndex, secondIndex, mem);
return mem[a][b][c][k] = (pick + skip) % kMod;
}
private int hash(int x) {
return x + 1;
}
}
// code provided by PROGIEZ3098. Find the Sum of Subsequence Powers LeetCode Solution in Python
class Solution:
def sumOfPowers(self, nums: list[int], k: int) -> int:
kMod = 1_000_000_007
nums.sort()
@functools.lru_cache(None)
def dp(
i: int,
k: int,
lastPickedIndex: int,
firstIndex: int,
secondIndex: int
) -> int:
if k == 0:
return nums[secondIndex] - nums[firstIndex]
if i == len(nums):
return 0
newFirstIndex = firstIndex
newSecondIndex = secondIndex
if firstIndex == -1:
newFirstIndex = i
elif secondIndex == -1:
newSecondIndex = i
elif nums[i] - nums[lastPickedIndex] < nums[secondIndex] - nums[firstIndex]:
newFirstIndex = lastPickedIndex
newSecondIndex = i
pick = dp(i + 1, k - 1, i, newFirstIndex, newSecondIndex)
skip = dp(i + 1, k, lastPickedIndex, firstIndex, secondIndex)
return (pick + skip) % kMod
return dp(0, k, -1, -1, -1)
# 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.