2836. Maximize Value of Function in a Ball Passing Game LeetCode Solution
In this guide, you will get 2836. Maximize Value of Function in a Ball Passing Game LeetCode Solution with the best time and space complexity. The solution to Maximize Value of Function in a Ball Passing Game 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 Maximize Value of Function in a Ball Passing Game
You are given an integer array receiver of length n and an integer k. n players are playing a ball-passing game.
You choose the starting player, i. The game proceeds as follows: player i passes the ball to player receiver[i], who then passes it to receiver[receiver[i]], and so on, for k passes in total. The game’s score is the sum of the indices of the players who touched the ball, including repetitions, i.e. i + receiver[i] + receiver[receiver[i]] + … + receiver(k)[i].
Return the maximum possible score.
Notes:
receiver may contain duplicates.
receiver[i] may be equal to i.
Example 1:
Input: receiver = [2,0,1], k = 4
Output: 6
Explanation:
Starting with player i = 2 the initial score is 2:
Pass
Sender Index
Receiver Index
Score
1
2
1
3
2
1
0
3
3
0
2
5
4
2
1
6
Example 2:
Input: receiver = [1,1,1,2,3], k = 3
Output: 10
Explanation:
Starting with player i = 4 the initial score is 4:
1 <= receiver.length == n <= 105
0 <= receiver[i] <= n – 1
1 <= k <= 1010
Complexity Analysis
Time Complexity: O(n\log k)
Space Complexity: O(n\log k)
2836. Maximize Value of Function in a Ball Passing Game LeetCode Solution in C++
class Solution {
public:
long long getMaxFunctionValue(vector<int>& receiver, long long k) {
const int n = receiver.size();
const int m = log2(k) + 1;
long ans = 0;
// jump[i][j] := the the node you reach after jumping 2^j steps from i
vector<vector<int>> jump(n, vector<int>(m));
// sum[i][j] := the sum of the first 2^j nodes you reach when jumping from i
vector<vector<long>> sum(n, vector<long>(m));
for (int i = 0; i < n; ++i) {
jump[i][0] = receiver[i];
sum[i][0] = receiver[i];
}
// Calculate binary lifting.
for (int j = 1; j < m; ++j)
for (int i = 0; i < n; ++i) {
const int midNode = jump[i][j - 1];
// the the node you reach after jumping 2^j steps from i
// = the node you reach after jumping 2^(j - 1) steps from i
// + the node you reach after jumping another 2^(j - 1) steps
jump[i][j] = jump[midNode][j - 1];
// the sum of the first 2^j nodes you reach when jumping from i
// = the sum of the first 2^(j - 1) nodes you reach when jumping from i
// + the sum of another 2^(j - 1) nodes you reach
sum[i][j] = sum[i][j - 1] + sum[midNode][j - 1];
}
for (int i = 0; i < n; ++i) {
long currSum = i;
int currPos = i;
for (int j = 0; j < m; ++j)
if (k >> j & 1) {
currSum += sum[currPos][j];
currPos = jump[currPos][j];
}
ans = max(ans, currSum);
}
return ans;
}
}; /* code provided by PROGIEZ */
2836. Maximize Value of Function in a Ball Passing Game LeetCode Solution in Java
class Solution {
public long getMaxFunctionValue(List<Integer> receiver, long k) {
final int n = receiver.size();
final int m = (int) (Math.log(k) / Math.log(2)) + 1;
long ans = 0;
// jump[i][j] := the the node you reach after jumping 2^j steps from i
int[][] jump = new int[n][m];
// sum[i][j] := the sum of the first 2^j nodes you reach when jumping from i
long[][] sum = new long[n][m];
for (int i = 0; i < n; ++i) {
jump[i][0] = receiver.get(i);
sum[i][0] = receiver.get(i);
}
// Calculate binary lifting.
for (int j = 1; j < m; ++j)
for (int i = 0; i < n; ++i) {
final int midNode = jump[i][j - 1];
// the the node you reach after jumping 2^j steps from i
// = the node you reach after jumping 2^(j - 1) steps from i
// + the node you reach after jumping another 2^(j - 1) steps
jump[i][j] = jump[midNode][j - 1];
// the sum of the first 2^j nodes you reach when jumping from i
// = the sum of the first 2^(j - 1) nodes you reach when jumping from i
// + the sum of another 2^(j - 1) nodes you reach
sum[i][j] = sum[i][j - 1] + sum[midNode][j - 1];
}
for (int i = 0; i < n; ++i) {
long currSum = i;
int currPos = i;
for (int j = 0; j < m; ++j)
if ((k >> j & 1) == 1) {
currSum += sum[currPos][j];
currPos = jump[currPos][j];
}
ans = Math.max(ans, currSum);
}
return ans;
}
} // code provided by PROGIEZ
2836. Maximize Value of Function in a Ball Passing Game LeetCode Solution in Python
class Solution:
def getMaxFunctionValue(self, receiver: list[int], k: int) -> int:
n = len(receiver)
m = int(math.log2(k)) + 1
ans = 0
# jump[i][j] := the the node you reach after jumping 2^j steps from i
jump = [[0] * m for _ in range(n)]
# summ[i][j] := the sum of the first 2^j nodes you reach when jumping from i
summ = [[0] * m for _ in range(n)]
for i in range(n):
jump[i][0] = receiver[i]
summ[i][0] = receiver[i]
# Calculate binary lifting.
for j in range(1, m):
for i in range(n):
midNode = jump[i][j - 1]
# the the node you reach after jumping 2^j steps from i
# = the node you reach after jumping 2^(j - 1) steps from i
# + the node you reach after jumping another 2^(j - 1) steps
jump[i][j] = jump[midNode][j - 1]
# the sum of the first 2^j nodes you reach when jumping from i
# = the sum of the first 2^(j - 1) nodes you reach when jumping from i
# + the sum of another 2^(j - 1) nodes you reach
summ[i][j] = summ[i][j - 1] + summ[midNode][j - 1]
for i in range(n):
currSum = i
currPos = i
for j in range(m):
if (k >> j) & 1 == 1:
currSum += summ[currPos][j]
currPos = jump[currPos][j]
ans = max(ans, currSum)
return ans # code by PROGIEZ
