Maximize Value of Function in a Ball Passing Game — LeetCode 2836 Python Solution
HardBit ManipulationArrayDynamic Programming
- Problem
- #2836
- Pattern
- Bit Manipulation
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given an integer array receiver of length n and an integer k. n players are playing a ball-passing game.
Python solution
Python
class Solution:
def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
n, m = len(receiver), k.bit_length()
f = [[0] * m for _ in range(n)]
g = [[0] * m for _ in range(n)]
for i, x in enumerate(receiver):
f[i][0] = x
g[i][0] = i
for j in range(1, m):
for i in range(n):
f[i][j] = f[f[i][j - 1]][j - 1]
g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1]
ans = 0
for i in range(n):
p, t = i, 0
for j in range(m):
if k >> j & 1:
t += g[p][j]
p = f[p][j]
ans = max(ans, t + p)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log k) |
| Space | O(n \times \log k) auxiliary |
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2836. Maximize Value of Function in a Ball Passing Game is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2836. Maximize Value of Function in a Ball Passing Game?
- LeetCode 2836. Maximize Value of Function in a Ball Passing Game is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2836. Maximize Value of Function in a Ball Passing Game?
- The Python solution on this page runs in O(n \times \log k).
- What is the space complexity of LeetCode 2836. Maximize Value of Function in a Ball Passing Game?
- The Python solution on this page uses O(n \times \log k) auxiliary space.
- What topics does LeetCode 2836. Maximize Value of Function in a Ball Passing Game cover?
- LeetCode 2836. Maximize Value of Function in a Ball Passing Game is tagged Bit Manipulation, Array and Dynamic Programming on LeetCode.