Please read the new rule regarding the restriction on the use of AI tools. ×

Minimum steps to make volume 0
Difference between en1 and en2, changed 4 character(s)
Can anybody help me with the following problem, it was asked in one of the OAs of Uber:↵
↵
You are given a cuboid with dimensions l, b and h. Your task is to make the volume equal to 0 in minimum possible steps. In each step you can reduce gcd(l,b,h) from either of l, b, or h.↵
↵
that is if you start with dimension l,b,h and gcd(l,b,h) = g, then in one step you can reach to any one of the following dimensions: ↵
↵
1) l-g, b, h↵
↵
2) l, b-g, h↵
↵
3) l, b, h-g↵
↵
Output the minimum number of steps required to reach a 0 volume cuboid.↵
The limit on l,b,h is not mentioned in the problem statement.↵
↵
I tried to solve this using 3D dp with l,b,h as states. But i got TLE on test-case: 9,24,35.↵
↵
Is there any other possible solutions available?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shpara 2024-06-09 19:41:33 4 Tiny change: '-g, b, h\n2) l, b-g, h\n3) l, b,' -> '-g, b, h\n\n2) l, b-g, h\n\n3) l, b,'
en1 English shpara 2024-06-09 19:40:52 774 Initial revision (published)