CodingHard
Minimum Smoke Mixture Problem
Filed under Amazon
Free read 3 of 3Use dp[i][j] to store the minimum smoke for the range [i, j].
The question
Given an array of volumes, find a mixing sequence that minimizes total smoke produced. Mixing two adjacent volumes a and b produces (a*b) smoke and results in a new volume (a+b)%100.
Constraints
- 1 <= volumes.length <= 100
- Volumes are between 0-99
- Minimize total smoke
Examples
- Input
- [40, 60, 20]
- Output
- 2400
- Why
- (40*60)=2400, smoke=2400, vol=0. (0*20)=0, total=2400.
Approach
Use dp[i][j] to store the minimum smoke for the range [i, j].
For range [i, j], split at k and calculate: dp[i][k] + dp[k+1][j] + (sum[i,k] * sum[k+1,j]).
Single elements produce 0 smoke.
Tips
- What they are testing: Test with small arrays and arrays where order of operations changes the result.
- Common mistake: Failing to recognize this as a variation of Matrix Chain Multiplication.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.