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:

  • receiver may contain duplicates.
  • receiver[i] may be equal to i.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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^5
  • 0 <= receiver[i] <= n - 1
  • 1 <= 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

  1. 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.
  2. For each starting player:
    • Use the binary representation of k to jump in powers of two, accumulating the score and updating the current player.
    • Track the maximum score across all starting players.
  3. Return the maximum score found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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.