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?
Auto comment: topic has been updated by shpara (previous revision, new revision, compare).