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?
↵
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?
