Maximize Value of Function in a Ball Passing Game
HardUpdated: Aug 2, 2025
Practice on:
Problem
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:
receivermay contain duplicates.receiver[i]may be equal toi.
Examples
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:
Pass | Sender Index | Receiver Index | Score
---|---|---|---
1 | 4 | 3 | 7
2 | 3 | 2 | 9
3 | 2 | 1 | 10
Constraints
1 <= receiver.length == n <= 10^50 <= receiver[i] <= n - 11 <= k <= 1010
Solution
Method 1 – Binary Lifting (Fast Path Simulation)
Intuition
This problem is a variation of the k-th ancestor problem, where we want to simulate k steps efficiently. By precomputing where the ball will be after 2^j passes for each player, we can use binary lifting to quickly compute the total score for any starting player and any k.
Approach
- Precompute for each player and each power of two (up to 2^40):
- The next player after 2^j passes.
- The sum of indices along the path of 2^j passes.
- For each starting player:
- Use the binary representation of
kto jump in powers of two, accumulating the score and updating the current player. - Track the maximum score across all starting players.
- Use the binary representation of
- Return the maximum score found.
Code
C++
class Solution {
public:
long long getMaxFunctionValue(vector<int>& receiver, long long k) {
int n = receiver.size(), LOG = 41;
vector<vector<int>> jump(n, vector<int>(LOG));
vector<vector<long long>> sum(n, vector<long long>(LOG));
for (int i = 0; i < n; ++i) {
jump[i][0] = receiver[i];
sum[i][0] = receiver[i];
}
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i < n; ++i) {
jump[i][j] = jump[jump[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[jump[i][j-1]][j-1];
}
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
long long score = i, rem = k;
int pos = i;
for (int j = LOG-1; j >= 0; --j) {
if ((rem >> j) & 1) {
score += sum[pos][j];
pos = jump[pos][j];
}
}
ans = max(ans, score);
}
return ans;
}
};
Go
func getMaxFunctionValue(receiver []int, k int64) int64 {
n, LOG := len(receiver), 41
jump := make([][]int, n)
sum := make([][]int64, n)
for i := range jump {
jump[i] = make([]int, LOG)
sum[i] = make([]int64, LOG)
jump[i][0] = receiver[i]
sum[i][0] = int64(receiver[i])
}
for j := 1; j < LOG; j++ {
for i := 0; i < n; i++ {
jump[i][j] = jump[jump[i][j-1]][j-1]
sum[i][j] = sum[i][j-1] + sum[jump[i][j-1]][j-1]
}
}
var ans int64
for i := 0; i < n; i++ {
score, pos, rem := int64(i), i, k
for j := LOG - 1; j >= 0; j-- {
if (rem>>j)&1 == 1 {
score += sum[pos][j]
pos = jump[pos][j]
}
}
if score > ans {
ans = score
}
}
return ans
}
Java
class Solution {
public long getMaxFunctionValue(int[] receiver, long k) {
int n = receiver.length, LOG = 41;
int[][] jump = new int[n][LOG];
long[][] sum = new long[n][LOG];
for (int i = 0; i < n; ++i) {
jump[i][0] = receiver[i];
sum[i][0] = receiver[i];
}
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i < n; ++i) {
jump[i][j] = jump[jump[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[jump[i][j-1]][j-1];
}
}
long ans = 0;
for (int i = 0; i < n; ++i) {
long score = i, rem = k;
int pos = i;
for (int j = LOG-1; j >= 0; --j) {
if (((rem >> j) & 1) == 1) {
score += sum[pos][j];
pos = jump[pos][j];
}
}
ans = Math.max(ans, score);
}
return ans;
}
}
Kotlin
class Solution {
fun getMaxFunctionValue(receiver: IntArray, k: Long): Long {
val n = receiver.size
val LOG = 41
val jump = Array(n) { IntArray(LOG) }
val sum = Array(n) { LongArray(LOG) }
for (i in 0 until n) {
jump[i][0] = receiver[i]
sum[i][0] = receiver[i].toLong()
}
for (j in 1 until LOG) {
for (i in 0 until n) {
jump[i][j] = jump[jump[i][j-1]][j-1]
sum[i][j] = sum[i][j-1] + sum[jump[i][j-1]][j-1]
}
}
var ans = 0L
for (i in 0 until n) {
var score = i.toLong()
var pos = i
var rem = k
for (j in LOG-1 downTo 0) {
if ((rem shr j) and 1L == 1L) {
score += sum[pos][j]
pos = jump[pos][j]
}
}
ans = maxOf(ans, score)
}
return ans
}
}
Python
class Solution:
def getMaxFunctionValue(self, receiver: list[int], k: int) -> int:
n, LOG = len(receiver), 41
jump = [[0]*LOG for _ in range(n)]
s = [[0]*LOG for _ in range(n)]
for i in range(n):
jump[i][0] = receiver[i]
s[i][0] = receiver[i]
for j in range(1, LOG):
for i in range(n):
jump[i][j] = jump[jump[i][j-1]][j-1]
s[i][j] = s[i][j-1] + s[jump[i][j-1]][j-1]
ans = 0
for i in range(n):
score, pos, rem = i, i, k
for j in range(LOG-1, -1, -1):
if (rem >> j) & 1:
score += s[pos][j]
pos = jump[pos][j]
ans = max(ans, score)
return ans
Rust
impl Solution {
pub fn get_max_function_value(receiver: Vec<i32>, k: i64) -> i64 {
let n = receiver.len();
let log = 41;
let mut jump = vec![vec![0; log]; n];
let mut sum = vec![vec![0i64; log]; n];
for i in 0..n {
jump[i][0] = receiver[i] as usize;
sum[i][0] = receiver[i] as i64;
}
for j in 1..log {
for i in 0..n {
jump[i][j] = jump[jump[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[jump[i][j-1]][j-1];
}
}
let mut ans = 0i64;
for i in 0..n {
let mut score = i as i64;
let mut pos = i;
let mut rem = k;
for j in (0..log).rev() {
if (rem >> j) & 1 == 1 {
score += sum[pos][j];
pos = jump[pos][j];
}
}
ans = ans.max(score);
}
ans
}
}
TypeScript
class Solution {
getMaxFunctionValue(receiver: number[], k: number): number {
const n = receiver.length, LOG = 41;
const jump = Array.from({length: n}, () => Array(LOG).fill(0));
const sum = Array.from({length: n}, () => Array(LOG).fill(0));
for (let i = 0; i < n; ++i) {
jump[i][0] = receiver[i];
sum[i][0] = receiver[i];
}
for (let j = 1; j < LOG; ++j) {
for (let i = 0; i < n; ++i) {
jump[i][j] = jump[jump[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[jump[i][j-1]][j-1];
}
}
let ans = 0;
for (let i = 0; i < n; ++i) {
let score = i, pos = i, rem = k;
for (let j = LOG-1; j >= 0; --j) {
if ((rem >> j) & 1) {
score += sum[pos][j];
pos = jump[pos][j];
}
}
ans = Math.max(ans, score);
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * log k), since for each player, we process up to log(k) jumps. - 🧺 Space complexity:
O(n * log k), for the binary lifting tables.