MediumNo. 0553
Optimal Division — LeetCode 553 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Math, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array nums. The adjacent integers in nums will perform the float division.
Example
- Input
- nums = [1000,100,10,2]
- Output
- "1000/(100/10/2)"
- Explanation
- 1000/(100/10/2) = 1000/((100/10)/2) = 200
Python solution
class Solution:
def optimalDivision(self, nums: List[int]) -> str:
n = len(nums)
if n == 1:
return str(nums[0])
if n == 2:
return f'{nums[0]}/{nums[1]}'
return f'{nums[0]}/({"/".join(map(str, nums[1:]))})'Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 553. Optimal Division is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0313 | Super Ugly Number | Medium |
| 0368 | Largest Divisible Subset | Medium |
| 0396 | Rotate Function | Medium |
| 0486 | Predict the Winner | Medium |
| 0805 | Split Array With Same Average | Hard |
| 0877 | Stone Game | Medium |
Frequently asked questions
- How hard is LeetCode 553. Optimal Division?
LeetCode 553. Optimal Division is rated Medium on LeetCode.
- What topics does LeetCode 553. Optimal Division cover?
LeetCode 553. Optimal Division is tagged Array, Math and Dynamic Programming on LeetCode.