← Amazon questions
CodingHard

Minimum Smoke Mixture Problem

Filed under Amazon

Free read 3 of 3

Use 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

  1. Use dp[i][j] to store the minimum smoke for the range [i, j].

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.