I recently attended HackWithInfy Round 2 and this was one of the questions they asked.
Two numbers will be given A and B. Constraints: 1<=A,B<=10^18.
Four operations are allowed:
- If a number is odd, you can subtract 1 from it
- If a number is even, you can add 1 to it
- If a number is even or odd, you can multiply 2 to it
- If a number is even, you can divide it by 2
What is the minimum number of operations to reach B from A. If not possible, just print 1.
I tried this with recursion and it gave TLE for large numbers. I couldn’t do using memorization also. If anyone came up with a better approach, please share it here.
The Number Game